[编程题]裁减网格纸
- 热度指数：21558 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
度度熊有一张网格纸，但是纸上有一些点过的点，每个点都在网格点上，若把网格看成一个坐标轴平行于网格线的坐标系的话，每个点可以用一对整数x，y来表示。度度熊必须沿着网格线画一个正方形，使所有点在正方形的内部或者边界。然后把这个正方形剪下来。问剪掉正方形的最小面积是多少。
输入描述:
第一行一个数n(2≤n≤1000)表示点数，接下来每行一对整数xi,yi(－1e9<=xi,yi<=1e9)表示网格上的点
输出描述:
一行输出最小面积
示例1
输入
2 0 0 0 3
输出
9
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int maxX = Integer.MIN_VALUE;
int maxY = Integer.MIN_VALUE;
int minX = Integer.MAX_VALUE;
int minY = Integer.MAX_VALUE;
for(int i = 0;i<n;i++){
int x = in.nextInt();
int y = in.nextInt();
maxX = (int) Math.max(maxX,x);
maxY = (int) Math.max(maxY,y);
minX = (int) Math.min(minX,x);
minY = (int) Math.min(minY,y);
}
int side = Math.max((maxX-minX),(maxY-minY));
System.out.println(side*side);
}
}
}
编辑于 2016-04-13 11:14:54
回复(8)
//运行通过
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
int main()
{
int number;
while (cin >> number)
{
int *xptr = new int[number];
int *yptr = new int[number];
for (int i = 0; i < number; ++i)
cin >> xptr[i] >> yptr[i];
int minX, minY, maxX, maxY;
minX = maxX = xptr[0];
minY = maxY = yptr[0];
for (int i = 1; i < number; ++i)
{
if (xptr[i] < minX)minX = xptr[i];
if (maxX < xptr[i])maxX = xptr[i];
if (yptr[i] < minY)minY = yptr[i];
if (maxY < yptr[i])maxY = yptr[i];
}
int xLength = maxX - minX;
int yLength = maxY - minY;
int minArea;
if (xLength>yLength)
minArea = xLength*xLength;
else minArea = yLength*yLength;
delete[]xptr;
delete[]yptr;
cout << minArea << endl;
}
return 0;
}
发表于 2015-10-05 14:35:45
回复(0)
这道题目原理还是很简单的，即x或y差的最大值 #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//测试用例比较大的时候，根本就不会提示输出是什么，系统的缓冲buffer有限
int main()
{
int n;
while(cin >> n)
{
//完成输入
vector<int> gridX;
vector<int> gridY;
while(n-- >0)
{
int x,y;
cin >> x >> y;
gridX.push_back(x);
gridY.push_back(y);
}
//计算边长，原理为x或y差的最大值
sort(gridX.begin(),gridX.end());
sort(gridY.begin(),gridY.end());
int edge = max(gridX.back() - gridX.front() ,gridY.back() - gridY.front());
cout << edge*edge<<endl;
}
}
发表于 2017-02-21 10:16:10
回复(3)
其实就是求最大x和最小x的差 以及最大y和最小y的差 比较哪个更大 然后平方 注意需要处理多组数据
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
//常量区
//函数区
//main函数
int main(){
int n, ro, co;
int max_x, max_y, min_x, min_y;
while(scanf("%d", &n) == 1){
max_x = max_y = -1e9 - 1;
min_x = min_y = 1e9 + 1;
for(int i=0; i<n; i++){
scanf("%d%d", &ro, &co);
max_x = max(max_x, ro);
max_y = max(max_y, co);
min_x = min(min_x, ro);
min_y = min(min_y, co);
}
int the_max = max(max_x - min_x, max_y - min_y);
printf("%d\n", the_max*the_max);
}
return 0;
}
发表于 2018-09-02 16:51:00
回复(0)
//最大的x点距离，和最大的y点距离
#include<stdio.h>
#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;
int main(){
int n;
while(cin>>n){
vector<int> x(n,0);
vector<int> y(n,0);
int xmin = INT_MAX;
int xmax = INT_MIN;
int ymin = INT_MAX;
int ymax = INT_MIN;
for(int i=0; i<n; ++i){
cin >> x[i];
cin >> y[i];
xmin = min(x[i],xmin);
xmax = max(x[i],xmax);
ymin = min(y[i],ymin);
ymax = max(y[i],ymax);
}
int k = max(xmax-xmin,ymax-ymin);
cout << k*k <<endl;
}
}
发表于 2016-09-03 19:37:19
回复(0)
# -*- coding:utf-8 -*-
while 1:
try:
s = raw_input()
except:
break
n = int(s)
for i in range(n):
x, y = map(int, raw_input().split())
if i == 0:
d = [x, x, y, y]
else:
if x < d[0]:
d[0] = x
if x > d[1]:
d[1] = x
if y < d[2]:
d[2] = y
if y > d[3]:
d[3] = y
print max(d[1] - d[0], d[3] - d[2]) ** 2
编辑于 2017-04-30 13:56:47
回复(1)
分别求出横纵坐标覆盖的范围，将正方形的边长取为两者中大的那个即可
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
int n, maxX, minX, maxY, minY;
while((line = br.readLine()) != null) {
n = Integer.parseInt(line);
maxX = Integer.MIN_VALUE;
maxY = Integer.MIN_VALUE;
minX = Integer.MAX_VALUE;
minY = Integer.MAX_VALUE;
for(int i = 0; i < n; i++){
String[] pos = br.readLine().split(" ");
minX = Math.min(Integer.parseInt(pos[0]), minX);
maxX = Math.max(Integer.parseInt(pos[0]), maxX);
minY = Math.min(Integer.parseInt(pos[1]), minY);
maxY = Math.max(Integer.parseInt(pos[1]), maxY);
}
int edge = Math.max(maxX - minX, maxY - minY);
System.out.println(edge*edge);
}
}
}
发表于 2021-02-26 13:19:52
回复(0)
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
struct Point2d{
int x,y;
};
int main()
{
int num;
while(cin>>num)
{
vector<Point2d> v(num);
for(int i=0;i<num;i++)
cin>>v[i].x>>v[i].y;
int max_x=INT_MIN;
int min_x=INT_MAX;
int max_y=INT_MIN;
int min_y=INT_MAX;
for(int i=0;i<num;i++)
{
max_x=max(v[i].x,max_x);
min_x=min(v[i].x,min_x);
max_y=max(v[i].y,max_y);
min_y=min(v[i].y,min_y);
}
if(abs(max_x-min_x)>abs(max_y-min_y))
cout<<(max_x-min_x)*(max_x-min_x)<<endl;
else
cout<<(max_y-min_y)*(max_y-min_y)<<endl;
}
return 0;
}
发表于 2018-01-25 10:11:50
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{ int n,x[1010],y[1010]; while(cin>>n) { int minX=INT_MAX,maxX=INT_MIN,minY=INT_MAX,maxY=INT_MIN; for(int i=0;i<n;i++) { cin>>x[i]>>y[i]; minX = (x[i]<minX)?x[i]:minX; maxX = (x[i]>maxX)?x[i]:maxX; minY = (y[i]<minY)?y[i]:minY; maxY = (y[i]>maxY)?y[i]:maxY; } int L = max(maxX-minX, maxY-minY); cout<<L*L<<endl; } return 0;
}
发表于 2017-10-25 01:42:50
回复(0)
import java.util.*;
public class Main{
public static void main (String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int[][] point= new int [n][2];
for(int i=0;i<n;i++){
point[i][0]=in.nextInt();
point[i][1]=in.nextInt();
}
int minLeft = point[0][0];
int maxLeft = point[0][0];
int minRight = point[0][1];
int maxRight = point[0][1];
for(int i=0;i<n;i++){
if (point[i][0]>maxLeft){
maxLeft=point[i][0];
}
if (point[i][0]<minLeft){
minLeft=point[i][0];
}
if (point[i][1]>maxRight){
maxRight=point[i][1];
}
if (point[i][1]<minRight){
minRight=point[i][1];
}
}
int rect=Math.max(Math.abs(maxRight-minRight),Math.abs(maxLeft-minLeft));
System.out.println(rect*rect);
}
}
}
发表于 2017-08-07 16:37:49
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef struct Point
{
int x;
int y;
}Point;
bool LessCompX(Point a, Point b)
{
return (a.x<b.x);
}
bool LessCompY(Point a, Point b)
{
return (a.y<b.y);
}
int main()
{
int n;
while (cin >> n)
{
Point p;
vector<Point> vec;
for (int i = 0; i<n; i++)
{
cin >> p.x >> p.y;
vec.push_back(p);
}
sort(vec.begin(), vec.end(), LessCompX);
int xMin = vec[0].x;
int xMax = vec[n - 1].x;
sort(vec.begin(), vec.end(), LessCompY);
int yMin = vec[0].y;
int yMax = vec[n - 1].y;
int Area;
if (abs(xMax - xMin) >= abs(yMax - yMin))
Area = abs(xMax - xMin)*abs(xMax - xMin);
else
Area = abs(yMax - yMin)*abs(yMax - yMin);
cout << Area << endl;
}
}
发表于 2017-07-31 14:45:30
回复(0)
#include<iostream>
using namespace std;
int main()
{
int N;
while (cin >> N)
{
int x, y;
cin >> x >> y;
int xi = x, yi = y, xa = x, ya = y;
for (int i = 1; i < N; i++)
{
cin >> x >> y;
if (x < xi)
xi = x;
else if (x>xa)
xa = x;
if (y < yi)
yi = y;
else if (y>ya)
ya = y;
}
if (ya - yi > xa - xi)
cout << (ya - yi)*(ya - yi) << endl;
else
cout << (xa - xi)*(xa - xi) << endl;
}
return 0;
}
发表于 2017-06-17 17:17:20
回复(0)
#include<iostream>
using namespace std;
int main(){
int n,x,y,min_x,max_x,min_y,max_y;
while(cin>>n){
for(int i=0;i<n;i++){
cin>>x>>y;
min_x=(i==0||x<min_x)?x:min_x;
max_x=(i==0||x>max_x)?x:max_x;
min_y=(i==0||y<min_y)?y:min_y;
max_y=(i==0||y>max_y)?y:max_y;
}
int r=max(max_x-min_x,max_y-min_y);
cout<<r*r<<endl;
}
return 0;
}
我只解释一下min_x=(i==0||x<min_x)?x:min_x 这句，其它的类推。
因为仅当i=0(此时min_x还没有被赋值)，或者x<min_x时，min_x才会取x的值，否则不变。
编辑于 2017-04-25 20:50:39
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner s = new Scanner(System.in);
while(s.hasNext()){
int n = s.nextInt();
int[] x = new int[n];
int[] y = new int[n];
for(int i = 0; i < n; i++){
x[i] = s.nextInt();
y[i] = s.nextInt();
}
Arrays.sort(x);
Arrays.sort(y);
int edge = (x[n - 1] - x[0]) > (y[n - 1] - y[0]) ? (x[n - 1] - x[0]) : (y[n - 1] - y[0]);
System.out.println((int) Math.pow(edge, 2));
}
}
}
发表于 2017-03-28 19:30:16
回复(0)
#include <iostream>
using namespace std;
int main(){
int N;
while(cin>>N){
int x,y;
int min_x = (0x1<<31) - 1, max_x = 0x1<<31, min_y = (0x1<<31) - 1, max_y = 0x1<<31;
while(N--){
cin>>x>>y;
min_x = min(x, min_x);
max_x = max(x, max_x);
min_y = min(y, min_y);
max_y = max(y, max_y);
}
int len = max(max_x - min_x, max_y - min_y);
cout<<len*len<<endl;
}
return 0;
}
编辑于 2017-03-16 22:16:56
回复(0)
package com.jimmysun.baidu2016; import java.util.Scanner; public class GridPaper { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNextInt()) { int n = 0; int minX, minY, maxX, maxY, xlength, ylength; int result; n = scanner.nextInt(); Coordinate[] coordinates = new Coordinate[n]; for (int i = 0; i < coordinates.length; i++) { coordinates[i] = new Coordinate(); coordinates[i].setX(scanner.nextInt()); coordinates[i].setY(scanner.nextInt()); } minX = coordinates[0].getX(); maxX = coordinates[0].getX(); minY = coordinates[0].getY(); maxY = coordinates[0].getY(); for (int i = 1; i < coordinates.length; i++) { if (coordinates[i].getX() < minX) { minX = coordinates[i].getX(); } if (coordinates[i].getX() > maxX) { maxX = coordinates[i].getX(); } if (coordinates[i].getY() < minY) { minY = coordinates[i].getY(); } if (coordinates[i].getY() > maxY) { maxY = coordinates[i].getY(); } } xlength = maxX - minX; ylength = maxY - minY; if (xlength > ylength) { result = xlength * xlength; } else { result = ylength * ylength; } System.out.println(result); } } } class Coordinate { int x, y; public Coordinate() { x = 0; y = 0; } public int getX() { return x; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; } }
编辑于 2016-09-28 21:52:52
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-11-14 18:26:28 -
2022-09-13 19:50:33
-
2022-09-13 18:22:03
-
2022-09-13 15:56:41 -
2022-09-13 15:07:25
相关试题
-
评论(1)
-
评论(12)
-
评论(169) 来自百度2016研发工程师在...
-
评论(145) 来自百度2016研发工程师在...
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
