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

有一个城市需要修建,给你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)
首先考虑用长方形将所有点包括起来;
则长方形左边的边具有最小的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)
#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)
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)
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)
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)
发表于 今天 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)
一个Python版本
n = int(input())
pos_x = []
pos_y = []
for i in range(n):
    x,y = [int(x) for x in input().split()]
    pos_x.append(x)
    pos_y.append(y)

l = max(max(pos_x) - min(pos_x), max(pos_y) - min(pos_y))
print(l*l)


编辑于 2019-08-15 16:10:05 回复(0)
#53.33%,求大佬优化
def solution(questions, records,m):
    for q in questions:
        bits = [0 for i in range(m)]
        beg = q[0]-1
        end = q[1]
        count = 0
        for i in range(beg, end, 1):
            if bits[records[i]-1] != 1:
                count += 1
                bits[records[i]-1] = 1
        print(count)

if __name__ == '__main__':
    n, m = [int(x) for x in input().split()]
    records = [int(x) for x in input().split()]
    Q = int(input())
    questions = []
    for i in range(Q):
        questions.append([int(x) for x in input().split()])
    res = solution(questions, records,m)


发表于 2019-08-15 15:11:00 回复(0)
import sys if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    x_list = []
    y_list = [] for i in range(n):
        line = sys.stdin.readline().strip()
        loc = list(map(int, line.split()))
        x_list.append(loc[0])
        y_list.append(loc[1])
    x_dis = abs(max(x_list) - min(x_list))
    y_dis = abs(max(y_list) - min(y_list))
are = max(x_dis, y_dis) * max(x_dis, y_dis) print(are)
思路和代码应该没问题,通过率为0.00%,估计是超过题目的时间限制或者空间限制,求大佬指点
发表于 2019-08-14 23:36:04 回复(0)
N = int(input())
 
x = []
y = []
for i in range(N):
    s = list(map(int,input().split()))
    x.append(s[0])
    y.append(s[1])

a = max(max(x)-min(x),max(y)-min(y))
print(a**2)

发表于 2019-08-14 10:51:15 回复(0)
python版本的:

import math
N=int(input())
ordit=[]
i=0
while i<N:
    temp=input()
    temp1=temp.split(" ")
    for ii in range(len(temp1)):
        temp1[ii]=int(temp1[ii])
    ordit.append(temp1)
    i+=1

tampx=[]
tampy=[]
for  j in range(len(ordit)):
    tamp=ordit[j]
    tampx.append(tamp[0])
    tampy.append(tamp[1])
tampx1=min(tampx)
tampx2=max(tampx)
tampy1=min(tampy)
tampy2=max(tampy)
#tampx.sort()
#tampy.sort()
d=max(tampx2-tampx1,tampy2-tampy1)
result=(d)**2
print(result)



发表于 2019-08-14 09:12:34 回复(3)
#include<iostream>
#include<algorithm>
#include<climits>
 
usingnamespacestd;
 
intmain()
{
    intn;
   while(cin>>n)
   {
   longlongMin_x=INT_MAX; longlongMax_x=INT_MIN;
     longlongMin_y=INT_MAX; longlongMax_y=INT_MIN;
    for(inti=0;i<n;i++)
   {
        longlongx,y;
       cin>>x>>y;
       Min_x=min(Min_x,x) ;
       Max_x=max(Max_x,x) ;
       Min_y=min(Min_y,y);
       Max_y=max(Max_y,y);      
   }
     longlonglen=max(Max_x-Min_x,Max_y-Min_y);
    cout<<len*len<<endl;
   }
}
发表于 2019-08-13 22:00:45 回复(0)

热门推荐

通过挑战的用户