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

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


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


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

输入

2
0 0
2 2

输出

4
示例2

输入

2
0 0
0 3

输出

9
首先考虑用长方形将所有点包括起来;
则长方形左边的边具有最小的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-06 09:31:14 回复(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)
//大数相乘啊!!!朋友们。。。。
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)
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)
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>
#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)
#include <iostream>
#include <string>
using std::string;
#include <vector>
using std::vector;
#include <unordered_map>
using std::unordered_map;
#include <unordered_set>
using std::unordered_set;
#include <stack>
using std::stack;
#include <deque>
using std::deque;
#include <algorithm>
using std::swap;
#include <bitset>
#include <array>
using std::array;

using namespace std;


struct Point {
    long long x;
    long long y;
}point[2000];

bool cmpX(const Point a, const Point b) {
    return a.x > b.x;
}

bool cmpY(const Point a, const Point b) {
    return a.y > b.y;
}

bool cmpMINX(const Point a, const Point b) {
    return a.x < b.x;
}

bool cmpMINY(const Point a, const Point b) {
    return a.y < b.y;
}

int main() {
    //cout << "Hello World" << endl;
    int N;
    scanf("%d", &N);

    long long x, y;
    for(int i = 0; i < N; i++){
        scanf("%lld%lld", &x, &y);
        point[i].x = x;
        point[i].y = y;
    }

    sort(point, point + N, cmpX);
    long long maxX = point[0].x;
    sort(point, point + N, cmpY);
    long long maxY = point[0].y;
    sort(point, point + N, cmpMINX);
    long long minX = point[0].x;
    sort(point, point + N, cmpMINY);
    long long minY = point[0].y;

    long long Xvalue = maxX - minX;
    long long Yvalue = maxY - minY;
    if(Xvalue > Yvalue){
        printf("%lld\n", Xvalue * Xvalue);
    }else{

            printf("%lld\n", Yvalue * Yvalue);
        }


    return 0;
}

发表于 2019-08-13 21:52:02 回复(0)
var n = readline();
var x = [];
var y = [];
var maxx=0;
var maxy=0;
var minx=0;
var miny=0;
for(var i=0;i<n;i++){
    var line = readline().split(' ');
    x.push(line[0]);
    y.push(line[1]);
}

function searchMax(arr,max){
    for(var j=0;j<arr.length;j++){
        if(max<arr[j]){
            max=arr[j];
        }
    }
    return max;
}

function searchMin(arr,min){
    for(var k=0;k<arr.length;k++){
        if(min>arr[k]){
            min=arr[k];
        }
    }
    return min;
}

var sx = Math.abs(searchMax(x,maxx)-searchMin(x,minx));
var sy = Math.abs(searchMax(y,maxy)-searchMin(y,miny));

if(sx>sy){
    print(sx*sx);
}else{
    print(sy*sy);
}

有大神能帮看看是哪里错了吗
发表于 2019-08-11 21:11:12 回复(2)
  import java.util.ArrayList; import java.util.Scanner;  public class test1 { public static void main(String arge[]){
        Scanner sc=new Scanner(System.in);  System.out.println("请输入城市个数");  int number=sc.nextInt();  ArrayList<city> input=new ArrayList<>();  for(int i=0;i<number;i++){
            input.add(new city(sc.nextInt(),sc.nextInt(),i+1));  } //比较  int maxx=0;  int minx=0;  int maxy=0;  int miny=0;  for(int i=0;i<input.size()-1;i++){
            city c=input.get(i);  for(int j=i+1;j<input.size();j++){
                city b=input.get(j);  if(c.x>b.x){
                    maxx=c.x;  minx=b.x;  }else{
                    maxx=b.x;  minx=c.x;  } if(c.y>b.y){
                    maxy=c.y;  miny=b.y;  }else {
                    maxy=b.y;  miny=c.y;  }
            }
        } int xx=maxx-minx;  int yy=maxy-miny;  long Ss=xx*yy;  System.out.println("面积是:"+Ss);        } static class city{ int x;  int y;  int index;  public city(int x,int y,int index){ this.x=x;  this.y=y;  this.index=index;  }
    }
}
发表于 2019-08-10 18:43:30 回复(0)

热门推荐

通过挑战的用户