首页 > 试题广场 > 城市修建
[编程题]城市修建

有一个城市需要修建,给你N个民居的坐标X,Y,问把这么多民居全都包进城市的话,城市所需最小面积是多少(注意,城市为平行于坐标轴的正方形)


输入描述:
第一行为N,表示民居数目(2≤N≤1000)


输出描述:
城市所需最小面积
示例1

输入

2
0 0
2 2

输出

4
示例2

输入

2
0 0
0 3

输出

9
//大数相乘啊!!!朋友们。。。。
var num = readline();
var house_x = [],house_y = [],tmp;
while(tmp = readline()){
    tmp = tmp.split(' ');
    house_x.push(tmp[0]);
    house_y.push(tmp[1]);
}
if(num == house_x.length && num == house_y.length){
    getArea(house_x,house_y,num);
}

function getArea(house_x,house_y,num){
    if(num<2) {console.log(0);}
    else{
        house_x.sort((a,b)=>{return a-b});
        house_y.sort((a,b)=>{return a-b});
        var x = Math.abs(house_x[num-1]-house_x[0]);
        var y = Math.abs(house_y[num-1]-house_y[0]);
        var side = Math.max(x,y);
        //哦呵呵呵。。。。。居然还有大数相乘这种鬼,查了我一宿
        var result = multi(side.toString(),side.toString())
        console.log(result)
    }
    
}
function multi(a,b){
    var str1,str2,len1,len2,maxlen,result = [];
    str1 = a.split("").reverse(); 
    str2 = b.split("").reverse();
    len1 = str1.length;
        len2 = str2.length;
//因为要在下一步做累加,如果不初始化为0,result[]中的值会变为NaN
//因为未初始化的数组中的值为undefined
    for(var i = 0;i < len1;i++)
        for(var j = 0;j < len2;j++)
            result[i + j] = 0;
    for(var i = 0;i < len1;i++)
        for(var j = 0;j < len2;j++)
    //根据乘法的手动计算方式,在上下相同位上会有相加
            result[i + j] += parseInt(str1[i]) * parseInt(str2[j]);
    var n = result.length;
    for(var k = 0;k < n-1;k++)
    {
        var temp = result[k];
        if(temp >= 10)
        {
            result[k] = temp % 10;
            //JS中的"/"不是除法取整,会取得小数,所以要用Math.floor()
            result[k + 1] +=  parseInt(temp / 10);
        }
    }
    return result.reverse().join("");
}

发表于 2019-08-15 09:50:59 回复(0)
#include <iostream>
using namespace std;
long long max(int a, int b)
{
    return a > b ? a : b;
}
long long min(int a, int b)
{
    return a < b ? a : b;
}
int main()
{
    long long n = 0;
    long long x, y;
    long long min_x = 0, min_y = 0, max_x = 0, max_y = 0;
    cin >> n;
    cin >> x;
    cin >> y;
    max_x = min_x = x;
    max_y = min_y = y;
    while (cin)
    {
        cin >> x;
        cin >> y;
        max_x = max(x, max_x);
        max_y = max(y, max_y);
        min_x = min(x, min_x);
        min_y = min(y, min_y);
    }
    long long l = (max_x - min_x);
    long long ll = (max_y - min_y);
    long long lll = max(l, ll);
    long long llll = lll * lll;

    cout << llll << endl;
}

发表于 2019-08-03 18:25:55 回复(1)
首先考虑用长方形将所有点包括起来;
则长方形左边的边具有最小的x值,右边的边具有最大的x值;
同理,下边的边具有最小的y值,上边的边具有最大的y值;
|maxX-minX|即为横轴方向长方形的边长;
|maxY-minY|即为纵轴方向长方形的边长;
题目要求正方形,则取上两者较大的那个,平方即得正方形面积。
#include<iostream>
using namespace std;
const long long LONG_MIN=(1<<63);
const long long LONG_MAX=(1<<63)-1;
int main()
{
    long long num;
    long long x=0,y=0;
    long long minX=LONG_MAX,minY=LONG_MAX,maxX=LONG_MIN,maxY=LONG_MIN;
    cin>>num;
    for(long long i=0;i<num;i++)
    {
        cin>>x>>y;
        if(x<=minX)
            minX=x;
        if(x>=maxX)
            maxX=x;
        if(y<=minY)
            minY=y;
        if(y>=maxY)
            maxY=y;
    }
    long long xLength=abs(maxX-minX);
    long long yLength=abs(maxY-minY);
    long long edgeLength=xLength >= yLength ? xLength: yLength;
    cout<<edgeLength*edgeLength;
    return 0;
}

编辑于 2019-08-20 10:12:12 回复(0)
import java.util.Arrays;
import java.util.Scanner;
 
/**
 * @Author:likui
 * @PacakgeName:城市所需最小面积
 * @Description:
 * @Date:Created in 20:37 2019/8/9
 */
public class Main {
    public static long Way(long x[],long y[]){
        Arrays.sort(x);
        Arrays.sort(y);
        if (x.length<2||y.length<2)
            return 0;
        long x_length=Math.abs(x[x.length-1]-x[0]);
        long y_length=Math.abs(y[y.length-1]-y[0]);
        return Math.max(x_length,y_length);
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long X[]=new long[n];
        long Y[]=new long[n];
        for (int i = 0; i <n ; i++) {
            X[i]=sc.nextLong();
            Y[i]=sc.nextLong();
        }
        long res=Way(X,Y);
        System.out.println(res*res);
    }
}
得到x轴最小和最大值的差,得到y轴最小和最大值的差,比较两者,得到最大的那个,用它平方即可
编辑于 2019-08-13 19:47:50 回复(2)
#!/usr/bin/env python
# coding=utf-8
n=int(input())
ans=[]
foriinrange(n):
    (x, y)=map(int,input().split())
    ans.append((x, y))
 
min_x=min(x[0]forxinans)
max_x=max(x[0]forxinans)
min_y=min(x[1]forxinans)
max_y=max(x[1]forxinans)
 
area=pow(max(max_x-min_x, max_y-min_y),2)
print(area)
发表于 2019-07-31 16:32:38 回复(0)
#include<stdio.h>
 
struct Node
{
    long long x,y;
}d[2000];
 
int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        int i;
        memset(d,0,sizeof(d));
        long long max_x=0,max_y=0,min_x=0,min_y=0;
        for(i=0;i<n;i++)
        {
            scanf("%lld%lld",&d[i].x,&d[i].y);
            if(d[max_x].x<d[i].x)
                max_x=i;
             if(d[max_y].y<d[i].y)
                max_y=i;
            if(d[min_x].x>d[i].x)
                min_x=i;
             if(d[min_y].y>d[i].y)
                min_y=i;
        }
        long long area,a,b;
        a=d[max_x].x-d[min_x].x;
        b=d[max_y].y-d[min_y].y;
        if(a>b)
            area=a*a;
        else
            area=b*b;
        printf("%lld\n",area);
    }
    return 0;
}
发表于 2019-08-01 16:14:11 回复(0)
Python 3

n = int(input())
x = []
y = []
for i in range(n):
    x1,y1 = map(int,input().split(" "))
    x.append(x1)
    y.append(y1)
temp = max(max(x)-min(x),max(y)-min(y))
print(temp*temp)


发表于 2019-08-23 09:47:19 回复(0)
public int MaxArea(){
        // 获取个数
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] Xs = new int[n];
        int[] Ys = new int[n];
        int MaxX = Integer.MIN_VALUE;
        int MinX = Integer.MAX_VALUE;
        int MaxY = Integer.MIN_VALUE;
        int MinY = Integer.MAX_VALUE;
        for(int i=0 ; i<n ; i++){
            // 输入同时求得最值
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            if(x > MaxX){
                MaxX = x;
            }
            if(x < MinX){
                MinX = x;
            }
            if(y > MaxY){
                y = MaxY;
            }
            if(y < MinY){
                MinY = y;
            }
        }
        // 根据最值求面积
        int len_x = MaxX - MinX;
        int len_y = MaxY - MinY;
        return len_x > len_y?(len_x * len_x):(len_y * len_y);
    }

发表于 2019-09-06 17:10:22 回复(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
其实就是x轴存储一个最大值,最小值,y轴存储一个最大值,最小值, 然后大的差值相乘即可.

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        //1.接收输入
        Scanner sc = new Scanner(System.in);
        int number = sc.nextInt(); //居民数
        long[] rece = new long[number];//接收数组
        //第一组数据既是最大值,又是最小值
        long xMax=sc.nextLong();
        long yMax=sc.nextLong();
        long xMin=xMax;
        long yMin=yMax;
        long xhelp=0; long yhelp=0;
        for(int i = 1; i < rece.length; i++) {
            xhelp=sc.nextLong();
            if(xhelp>xMax) xMax=xhelp;
            if(xhelp<xMin) xMin=xhelp;
            yhelp=sc.nextLong();
            if(yhelp>yMax) yMax=yhelp;
            if(yhelp<yMin) yMin=yhelp;
        }
        long MaxSide=Math.abs(xMax-xMin)>Math.abs(yMax-yMin) ? Math.abs(xMax-xMin) : Math.abs(yMax-yMin);
        System.out.println(MaxSide*MaxSide);
    }
}


发表于 2019-08-30 21:15:47 回复(0)
Java实现
这题在循环读入的时候就应该找到最大最小的X和Y,这样节省时间。
import java.util.*;
public class Main{
    public static void main(String[] args) {
        System.out.println(constructCity());
    }
    public static long constructCity() {
        Scanner sc = new Scanner(System.in);
        int numHouse = sc.nextInt();
        int count = numHouse;
        long plotX,plotY,diffX,diffY;
        long maxX=0, maxY=0 ,minX=0, minY=0;
        while (count-- > 0) {
            if ((count + 1) == numHouse) {
                maxX = minX = sc.nextLong();
                maxY = minY = sc.nextLong();
                continue;
            }
            plotX = sc.nextLong();
            plotY = sc.nextLong();
            if (plotX > maxX || plotX < minX) {
                if (plotX > maxX) {
                    maxX = plotX;
                }
                if (plotX < minX) {
                    minX = plotX;
                }
            }
            if (plotY > maxY || plotY < minY) {
                if (plotY > maxY) {
                    maxY = plotY;
                }
                if (plotY < minY) {
                    minY = plotY;
                }
            }
        }
        diffX = Math.abs(maxX - minX);
        diffY = Math.abs(maxY - minY);
        return diffX > diffY? diffX*diffX:diffY*diffY;
    }
}


发表于 2019-08-10 09:41:08 回复(0)
#include<iostream>
#include<algorithm>
using namespace std;
 
int main(){
    //遍历所有居民的x的最小值和最大值,找到差值
    //遍历y的差值
    //找到x,y中大的,取平方
    int n;cin>>n;
    long long int X[n];
    long long int Y[n];
    for(int i=0;i<n;i++){
        cin>>X[i]>>Y[i];
    }
    sort(X,X+n);//默认从小到大排序,头文件是algorithm
    sort(Y,Y+n);
    long long int x=X[n-1]-X[0];
    long long int y=Y[n-1]-Y[0];
    long long int res=max(x,y)*max(x,y);//记住这里不能用pow(),否则会判错
    cout<<res<<endl;
}

发表于 2019-08-05 15:46:13 回复(0)
while True:
    try:
        N=int(input())
        x=[]
        y=[]
        fori inrange(N):
            s=input().split()
            x.append(int(s[0]))
            y.append(int(s[1]))
        x.sort()
        y.sort()
        res=max(x[-1]-x[0],y[-1]-y[0])
        print(res*res)
    except:
        break

发表于 2019-08-02 22:19:59 回复(0)
思路:由于城市是一个正方形且平行于坐标轴,还要包含所有的点,则正方形右上角顶点的x,y坐标必须分别大于等于n个点中最大的x坐标和y坐标,正方形左下角顶点的x,y坐标必须分别小于等于n个点中最小的x坐标和最小y坐标。正方形的边长即为n个点中最大、最小的x坐标的差值和最大、最小的y坐标的差值中更大的。
#include <bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (ll i=x;i<=y;i++)
typedef long long ll;
const int INF=2147000000;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int x,y,maxx=-1,maxy=-1,minx=INF,miny=INF;
    rep(i,1,n)
    {
        cin>>x>>y;
        maxx=max(maxx,x);
        minx=min(minx,x);
        maxy=max(maxy,y);
        miny=min(miny,y);
    }
    int ans;
    ans=max(maxx-minx,maxy-miny);
    cout<<ans*ans<<endl;
    return 0;
}
望采纳,谢谢~
发表于 2019-07-31 11:28:12 回复(0)
#include <iostream>
using namespace std;
 
int main(){
    long left = 0;
    long right = 0;
    long top = 0;
    long bottom = 0;
    int n = 0;
    cin >> n;
    int isfirst = 1;
    while(n>0){
        long x,y= 0;
        cin >> x >> y;
        if(isfirst == 1){
            isfirst = 0;
            left = x;
            right = x;
            bottom = y;
            top = y;
        }
        if(x<left)left = x;
        if(x>right)right = x;
        if(y<bottom)bottom = y;
        if(y>top)top = y;
        n--;
    }
    long edge_len = (right-left)>(top-bottom)?(right-left):(top-bottom);
    long result = edge_len*edge_len;
    cout << result << endl;
    return 0;
}


编辑于 2019-09-21 10:18:36 回复(0)
用例应该是有误的;
用例:
    2
    -545182011 148174425
    -819653699 414310201

    对应输出应该为:(这里的答案应该有误,准确答案应该是我的输出,说白了就是819653699的平方)

    75334707513569344

    你的输出为:

    671832186284382601
题目还是很简单的,注意一下大数的问题就行了
/*
  规则说白了,就是寻找最大X的长度,以及Y长度,然后找出最大的值进行平方  

*/
public class 城市修建 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        //这里区分一下正负,因为如果一正一负的话,那距离是正轴加负轴
        Long xPosMax = 0L;
        Long yPosMax = 0L;
        Long xNegMax = 0L;
        Long yNegMax = 0L;

        for (int i = 0; i < n; i++) {
            Long x = in.nextLong();

            if (x > 0) xPosMax = xPosMax > x ? xPosMax : x;
            if (x < 0) xNegMax = xNegMax < x ? xNegMax : x;

            Long y = in.nextLong();
            if (y > 0) yPosMax = yPosMax > y ? yPosMax : y;
            if (y < 0) yNegMax = yNegMax < y ? yNegMax : y;
        }
        
        Long x = xPosMax - xNegMax;
        Long y = yPosMax - yNegMax;
        
        //这里针对数据溢出问题直接使用了BigInteger,注意一下BigInteger没有减法,只有取反negate()
        BigInteger bigPosX = BigInteger.valueOf(xPosMax);
        BigInteger bigNegX = BigInteger.valueOf(xNegMax);
        BigInteger maxX = bigPosX.add(bigNegX.negate());

        BigInteger bigPosY = BigInteger.valueOf(yPosMax);
        BigInteger bigNegY = BigInteger.valueOf(yNegMax);
        BigInteger maxY = bigPosY.add(bigNegY.negate());


        if (x > y) System.out.println(maxX.pow(2));
        else System.out.println(maxY.pow(2));
    }


}



发表于 2019-09-17 09:58:22 回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    long point_num = 0;
    long temp_1 = 0, temp_2 = 0;
    long max_x = 0, min_x = 0;
    long max_y = 0, min_y = 0;
    long x_scale = 0, y_scale = 0;
    long res = 0, final_scale = 0;
    vector <long>  point_x;
    vector <long>  point_y;
    cin >> point_num;
    for (long i = 0; i < point_num; i++)
    {
        cin >> temp_1 >> temp_2;
        point_x.push_back(temp_1);
        point_y.push_back(temp_2);
    }
    max_x = *max_element(point_x.begin(), point_x.end());
    min_x = *min_element(point_x.begin(), point_x.end());
    max_y = *max_element(point_y.begin(), point_y.end());
    min_y = *min_element(point_y.begin(), point_y.end());

    x_scale = max_x - min_x;
    y_scale = max_y - min_y;

    final_scale = max(x_scale, y_scale);

    res = final_scale * final_scale;

    cout << res << endl;
}
发表于 2019-09-05 20:38:09 回复(0)
Ped头像 Ped

var n = readline();
var arrX = [];
var arrY = [];
while(line = readline()) {
    var lines = line.split(' ');
    var x = parseInt(lines[0]);
    var y = parseInt(lines[1]);
    arrX.push(x);
    arrY.push(y);
}
function area(arrX, arrY, n) {
    var maxLength = 0;
    arrX.sort((a,b)=>{return a-b});
    arrY.sort((a,b)=>{return a-b});
 
    var maxX = Math.abs(arrX[n - 1] - arrX[0]);
    var maxY = Math.abs(arrY[n - 1] - arrY[0]);
 
    maxLength = maxX > maxY ? maxX : maxY;
    return maxLength * maxLength;
}
print(area(arrX,arrY,n));

求助,我这个测试用例只通过26.27%,是那里需要改善吗?有没有做过的人帮忙指点一下?

编辑于 2019-09-28 19:56:34 回复(0)
num=int(input()) datas=list(map(int,input().strip().split(" ")))  row=datas[::2]  row.sort()  col=datas[1::2] col.sort() max=max(row[num-1],col[num-1]) print(max*max)
发表于 2019-08-24 10:12:14 回复(0)
import java.util.Scanner;
 
 
public class Main{
       
     
    public static void main(String[] args) {
        System.out.println("输入居民数量:");
        Scanner sc = new Scanner(System.in);
        int peoNum = sc.nextInt();
        int x0 = 0;
        int y0 = 0;
        int xx =1000;
        int yy =1000;
        /**
        其中x0,y0是初始化
        xx,yy是该城镇最大坐标
        */
        for(int i = 0;i<peoNum;i++){
            int x,y;
            System.out.println("输入x坐标:");
            x = sc.nextInt();
            System.out.println("输入y坐标:");
            y = sc.nextInt();
            xx = Math.min(xx, x);
            x0 = Math.max(x0, x);
            yy = Math.min(yy, y);
            y0 = Math.max(y0, y);
        }
        int area = (xx-x0)*(yy-y0);
        System.out.println("最小面积为:"+area);
                 
    }
}
问一下,为什么在着显示错误,在自己电脑上没有问题啊,求解
发表于 2019-08-21 11:46:03 回复(0)
#include <iostream>
#include <climits>
#include <algorithm>
 
using namespace std;
 
long long minArea(int& n)
{
    long long minx = INT64_MAX, miny = INT64_MAX, maxx = INT64_MIN, maxy = INT64_MIN;
 
    // 读入数据的时候就计算
    for (int i = 0; i < n; i++) {
        long long x, y;
        cin >> x >> y;
        minx = min(minx, x);
        miny = min(miny, y);
        maxx = max(maxx, x);
        maxy = max(maxy, y);
    }
 
    // 计算结果
    long long edge = max(abs(maxx - minx), abs(maxy - miny));
    return edge * edge;
}
 
int main()
{
    // 读入数据
    int n;
    cin >> n;
    cout << minArea(n) << endl;
    return 0;
}

发表于 2019-08-17 22:24:23 回复(0)