[编程题]最小长方形
- 热度指数：4529 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
给定一系列2维平面点的坐标(x, y)，其中x和y均为整数，要求用一个最小的长方形框将所有点框在内。长方形框的边分别平行于x和y坐标轴，点落在边上也算是被框在内。
输入描述:
测试输入包含若干测试用例，每个测试用例由一系列坐标组成，每对坐标占一行，其中|x|和|y|小于1e18；一对0 坐标标志着一个测试用例的结束。注意(0, 0)不作为任何一个测试用例里面的点。一个没有点的测试用例标志着整个输入的结束。
输出描述:
对每个测试用例，在1行内输出2对整数，其间用一个空格隔开。第1对整数是长方形框左下角的坐标，第2对整数是长方形框右上角的坐标。
示例1
输入
12 56 23 56 13 10 0 0 12 34 0 0 0 0
输出
12 10 23 56 12 34 12 34
import java.util.Scanner;
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int x = sc.nextInt();
int y = sc.nextInt();
List<Integer> xl = new ArrayList<>();
List<Integer> yl = new ArrayList<>();
while(x != 0 && y != 0){
xl.add(x);
yl.add(y);
x = sc.nextInt();
y = sc.nextInt();
}
Collections.sort(xl);
Collections.sort(yl);
System.out.println(xl.get(0)+" "+yl.get(0)+" "+xl.get(xl.size()-1)+" "+yl.get(yl.size()-1));
}
}
}
发表于 2018-10-22 15:26:41
回复(1)
不存入数组的方法：
#include
#include
int minx=INT_MAX, miny=INT_MAX, maxx=INT_MIN, maxy=INT_MIN;
void judge(int x,int y){
if(x<minx) minx=x;
if(x>maxx) maxx=x;
if(y<miny) miny=y;
if(y>maxy) maxy=y;
}
int main(){
int x,y;
while(~scanf("%d%d",&x,&y)&&(x||y)){
judge(x,y);
while(~scanf("%d%d",&x,&y)&&(x||y))
judge(x,y);
printf("%d %d %d %d\n",minx,miny,maxx,maxy);
}
return 0;
}
编辑于 2018-02-18 23:41:55
回复(0)
补充java版本，思路很清晰
package com.speical.first;
import java.util.Scanner;
/**
*
* @author special
* @date 2018年1月25日 上午11:30:46
*/
public class Pro147 {
static final int MIN = Integer.MIN_VALUE;
static final int MAX = Integer.MAX_VALUE;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
int n, m;
while(input.hasNext()){
n = input.nextInt();
m = input.nextInt();
if(n == 0 && m == 0) break;
int minX = MAX, maxX = MIN, minY = MAX, maxY = MIN;
while(!(n == 0 && m == 0)){
minX = Math.min(minX, n);
maxX = Math.max(maxX, n);
minY = Math.min(minY, m);
maxY = Math.max(maxY, m);
n = input.nextInt();
m = input.nextInt();
}
System.out.println(minX + " " + minY + " " + maxX + " " + maxY);
}
}
}
发表于 2018-01-25 11:40:03
回复(0)
python solution:
思路：把所有的坐标都保存到一个数组里面，左下角的坐标是（最小的横坐标，最小的纵坐标），右上角的坐标是（最大的横坐标，最大的纵坐标）。
当然要注意，当且仅当数组里面有数据时，才能进行输出，所以最终代码如下：
res = []
while True:
try:
a = input()
if a != "0 0":
res.append(list(map(int, a.split())))
elif res:
print(min(map(lambda c: c[0], res)), min(map(lambda c: c[1], res)), max(map(lambda c: c[0], res)), max(map(lambda c: c[1], res)))
res = []
except:
break
发表于 2017-10-25 15:00:19
回复(0)
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> X,Y;
int x,y;
while(cin>>x>>y&&x!=0&&y!=0) {
X.push_back(x);
Y.push_back(y);
}
sort(X.begin(),X.end());
sort(Y.begin(),Y.end());
printf("%d %d %d %d",*X.begin(),*Y.begin(),*(X.end()-1),*(Y.end()-1));
}
发表于 2020-03-28 11:47:32
回复(0)
温柔的题
#include <stdio.h>
int main()
{
int x, y;
int min_x, min_y, max_x, max_y;
while(scanf("%d %d", &x, &y)!=EOF)
{
if(x==0&&y==0) break;
min_x=x;
max_x=x;
min_y=y;
max_y=y;
while(scanf("%d %d", &x, &y)!=EOF)
{
if(x==0&&y==0) break;
if(x>max_x) max_x=x;
if(x<min_x) min_x=x;
if(y>max_y) max_y=y;
if(y<min_y) min_y=y;
}
printf("%d %d %d %d\n", min_x, min_y, max_x, max_y);
}
return 0;
}
发表于 2018-03-02 16:11:26
回复(1)
#include<stdio.h>
int main()
{
int x[462],y[462],n=0;
for(int i=0;;i++)
{
scanf("%d %d",&x[i],&y[i]);
if(x[i]==0&&y[i]==0)
break;
n=i+1;
}
int x1=x[0],x2=x[0],y1=y[0],y2=y[0];
for(int i=0;i<n;i++)
{
if(x[i]<x1)
x1=x[i];
if(x[i]>x2)
x2=x[i];
if(y[i]<y1)
y1=y[i];
if(y[i]>y2)
y2=y[i];
}
if(x[0]!=0&&y[0]!=0)
{
printf("%d %d %d %d",x1,y1,x2,y2);
}
}
发表于 2019-08-22 19:39:32
回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
long long x, y;
int count = 0;
vector<long long> rawList, colList;
while (cin >> x >> y) {
if (x == 0 && y == 0 && count == 0) {
break;
}
if (x == 0 && y == 0) {
// 结束了一轮输入，进行求值
sort(rawList.begin(), rawList.end());
sort(colList.begin(), colList.end());
cout << rawList[0] << " " << colList[0]<<" ";
cout << rawList[rawList.size() - 1] << " " << colList[colList.size() - 1];
rawList.clear();
colList.clear();
count = 0;
} else {
rawList.push_back(x);
colList.push_back(y);
count++;
}
}
return 0;
}
发表于 2021-01-15 16:07:56
回复(1)
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
struct node{
int xx,yy;
};
int main(){
int x,y,x0,y0,x1,y1;
vector<node> vn;
while(scanf("%d%d",&x,&y)!=EOF){
if(x==0 && y==0 && vn.size()==0) break;
else if(x==0 && y==0 && vn.size()!=0){
x0=vn[0].xx;
y0=vn[0].yy;
x1=vn[0].xx;
y1=vn[0].yy;
for(int i=1;i<vn.size();i++){
x0=min(x0,vn[i].xx);
y0=min(y0,vn[i].yy);
x1=max(x1,vn[i].xx);
y1=max(y1,vn[i].yy);
}
printf("%d %d %d %d\n",x0,y0,x1,y1);
vn.clear();
}else{
node n;
n.xx=x;
n.yy=y;
vn.push_back(n);
}
}
}
编辑于 2024-03-26 22:19:57
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x,y,flag=1;
while(flag)
{
int min_x=INT_MAX,min_y=INT_MAX,max_x=-INT_MAX,max_y=-INT_MAX;
int t=0;
while(cin>>x>>y)
{
if(x==0&&y==0)
{
if(t==0)
{
flag=0;
break;
}
else break;
}
else{
t=1;
min_x=min(min_x,x);
min_y=min(min_y,y);
max_x=max(max_x,x);
max_y=max(max_y,y);
}
}
if(flag)
cout<<min_x<<" "<<min_y<<" "<<max_x<<" "<<max_y<<endl;
}
return 0;
}
编辑于 2024-03-18 16:14:07
回复(0)
#include<stdio.h>
int main(){
int xmin,ymin;
int xmax,ymax;
int x,y;
int flag = 1;
while(scanf("%d %d",&x,&y)){
if(flag ==1){
xmin = x; xmax = x;
ymin = y; ymax = y;
flag = 0;
}
if(x==0&&y==0){
if(xmin==0&&xmax==0) return 0;
printf("%d %d %d %d\n",xmin,ymin,xmax,ymax); flag = 1;
}else{
if(x>xmax&&x!=0) xmax = x;
if(x<xmin&&x!=0) xmin = x;
if(ymin>y&&y!=0) ymin = y;
if(ymax<y&&y!=0) ymax = y;
}
}
}
发表于 2024-03-11 15:41:16
回复(0)
#include <climits>
#include <iostream>
using namespace std;
int main() {
while (true) {
long long x, y,
minX = LONG_MAX, minY = LONG_MAX,
maxX = LONG_MIN, maxY = LONG_MIN;
bool finish = true;
while (cin >> x >> y && x && y) {
finish = false;
if (x < minX) {
minX = x;
}
if (x > maxX) {
maxX = x;
}
if (y < minY) {
minY = y;
}
if (y > maxY) {
maxY = y;
}
}
if (finish) {
break;
}
cout << minX << " " << minY << " " << maxX << " " << maxY << endl;
}
return 0;
}
编辑于 2024-03-03 14:54:12
回复(0)
#include <iostream>
#include<limits.h>
#include<algorithm>
#include<math.h>
using namespace std;
int main() {
long long maxx = LLONG_MIN, maxy = LLONG_MIN, minx = LLONG_MAX,
miny = LLONG_MAX;
long long x, y;
bool flag = false; //看是不是第一组数据
while (cin >> x >> y) {
if (x == 0 && y == 0 && flag == false)
break;
else if (x == 0 && y == 0) { //结束这轮输入
cout << minx <<' '<< miny <<' '<< maxx <<' '<< maxy << endl;
maxx = LLONG_MIN, maxy = LLONG_MIN, minx = LLONG_MAX, miny = LLONG_MAX;
flag = false;
}
else {
flag = true;
maxx = max(maxx, x);
maxy = max(maxy, y);
miny = min(miny, y);
minx = min(minx, x);
}
}
}
发表于 2023-03-27 17:48:23
回复(0)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool comp(std::string a,std::string b){//a>b true else false
if(a[0]=='-'&&b[0]=='-') {//两个数都是负数时，先去负号
a=a.substr(1);
b=b.substr(1);
int m=a.size(),n=b.size();//将两个字符串长度补齐进行大小判断
if(m>n){
b.insert(0,m-n,'0');
}
else{
a.insert(0,n-m,'0');
}
return a>b;
}
else if(a[0]=='-'&&b[0]!='-')return false;
else if(a[0]!='-'&&b[0]=='-')return true;
else{
int m=a.size(),n=b.size();//将两个字符串长度补齐进行大小判断
if(m>n){
b.insert(0,m-n,'0');
}
else{
a.insert(0,n-m,'0');
}
return a>b;
}
}
int main(){
std::string tempx,tempy,x0,y0,x1,y1;//每次输入的string
std::vector<std::string> x,y;//用来存放所有数据的x和y坐标
while(std::cin >> tempx >>tempy ){
if(tempx=="0"&&tempy=="0"){//
x0="",y0="",x1="",y1="";//每次有00输入时初始化
for(int i=0;i<x.size();i++){//两个vector分别遍历，找出最小的x和y以及最大的x和y
if(comp(x0,x[i])||x0==""){
x0=x[i];
}
if(comp(x[i],x1)||x1==""){
x1=x[i];
}
}
for(int j=0;j<y.size();j++){
if(comp(y0,y[j])||y0==""){
y0=y[j];
}
if(comp(y[j],y1)||y1==""){
y1=y[j];
}
}
if(x0!=""&&y0!=""&&x1!=""&&y1!="") {//有可能连续两派00，只有有东西的情况下才需要打印。
std::cout << x0 << " " << y0 << " " << x1 << " " << y1 << std::endl;//输出结果
x.clear(), y.clear();//清空vector
}
else{
x.clear(), y.clear();//清空vector
}
}
else{
x.push_back(tempx);
y.push_back(tempy);
}
}
}
发表于 2023-03-21 15:03:43
回复(0)
#include <iostream>
#include <array>
using namespace std;
int main()
{
long x = 0, y= 0;
cin >> x >> y;
if (x == 0 && y == 0) return 0;
long minX = x, minY = y, maxX = x, maxY = y;
while(cin >> x >> y)
{
if (x == 0 && y == 0) break;
if (minX > x) minX = x;
if (minY > y) minY = y;
if (maxX < x) maxX = x;
if (maxY < y) maxY = y;
}
cout << minX << " " << minY << " " << maxX << " " << maxY << endl;
return 0;
}
发表于 2022-08-24 15:08:58
回复(0)
// 找出 x,y 的最大最小值
// 左下角坐标即 x_min, y_min
// 右上角坐标即 x_max, y_max
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
long long x, y;
// count 用于计数，判断是一个用例，还是输入的结束
int count = 0;
vector<long long> x_vec, y_vec;
while(cin >> x >> y){
// 输入结束
if(x == 0 && y == 0 && count ==0)
break;
// 一个用例结束
if(x == 0 && y == 0){
sort(x_vec.begin(), x_vec.end());
sort(y_vec.begin(), y_vec.end());
cout << x_vec[0] << " " << y_vec[0] << " ";
cout << x_vec.back() << " " << y_vec.back() << endl;
// 一个用例结束，要将向量清空，计数归0
x_vec.clear();
y_vec.clear();
count = 0;
}
else{
x_vec.push_back(x);
y_vec.push_back(y);
count++;
}
}
return 0;
}
发表于 2022-02-27 20:33:26
回复(0)
#include<stdio.h>
int main(){
int minx,miny,maxx,maxy;
int x,y;
int tag=0,tag2=0;
scanf("%d %d",&x,&y);
if(x!=0&&y!=0){
minx=x,maxx=x;
miny=y,maxy=y;
while(1){
scanf("%d %d",&x,&y);
if(tag==1){
minx=x,maxx=x;
miny=y,maxy=y;
}
if(x!=0&&y!=0){
if(maxx<x)maxx=x;
if(minx>x)minx=x;
if(maxy<y)maxy=y;
if(miny>y)miny=y;
tag=0;
tag2=0;
}
else{
tag2++;
if(tag2==2)break;
printf("%d %d %d %d\n",minx,miny,maxx,maxy);
tag=1;
}
}
}
else return 0;
}
发表于 2022-02-15 22:28:11
回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s;
while ((s = br.readLine()) != null) {
String[] ss = s.split(" ");
int xx = Integer.parseInt(ss[0]);
int yy = Integer.parseInt(ss[1]);
if (xx == 0 && yy == 0) break;//整个结束
ArrayList<Integer> xlist = new ArrayList<>();
ArrayList<Integer> ylist = new ArrayList<>();
while (!(xx == 0 && yy == 0)) {//只要没有0 0这个测试用例就没有结束，接着读数据
xlist.add(xx);
ylist.add(yy);
String[] str = br.readLine().split(" ");
xx = Integer.parseInt(str[0]);
yy = Integer.parseInt(str[1]);
}
xlist.sort((o1, o2) -> o1 - o2);
ylist.sort((o1, o2) -> o1 - o2);
System.out.println(xlist.get(0) + " " + ylist.get(0) + " " + xlist.get(xlist.size() - 1) + " " + ylist.get(xlist.size() - 1));
}
}
}
发表于 2021-04-12 20:18:12
回复(0)
#include<iostream>
#include<cstdio>
using namespace std;
int main() {
int x, y;
while(cin >> x >> y) {
if(x == 0 && y == 0) break;
int minx = x, miny = y;
int maxx = x, maxy = y;
while(cin >> x >> y) {
if(x == 0 && y == 0) break;
if(x < minx) minx = x;
if(y < miny) miny = y;
if(x > maxx) maxx = x;
if(y > maxy) maxy = y;
}
printf("%d %d %d %d\n", minx, miny, maxx, maxy);
}
return 0;
}
发表于 2021-02-10 19:51:24
回复(0)
我觉得我的代码没有问题，实际却无法通过。供大家参考下吧，逻辑输入和结束逻辑控制只用了一个while循环。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int x,y;
int minx = 0x1e18,miny = 0x1e18,maxx = -0x1e18,maxy = -0x1e18;
Scanner scanner = new Scanner(System.in);
boolean k = true;
boolean oneend = true;
while (k){
x = scanner.nextInt();
y = scanner.nextInt();
if(oneend && x == 0 && y == 0 ){
k = false;
}else{
if(x == 0 && y == 0){
//一组结束
oneend = true;
//System.out.println("一组结束");
System.out.println(String.format("%d %d %d %d",minx,miny,maxx,maxy));
minx = 0x1e18;miny = 0x1e18;maxx = -0x1e18;maxy = -0x1e18;
}else{
oneend = false;
if(x < minx){
minx = x;
}
if(y < miny){
miny = y;
}
if(x > maxx){
maxx = x;
}
if(y > maxy){
maxy = y;
}
}
}
}
}
}
发表于 2020-07-09 10:54:41
回复(0)
问题信息
难度：
40条回答
39收藏
5917浏览
通过挑战的用户
查看代码-
2023-02-28 11:05:09 -
2023-02-15 21:59:07
-
2023-01-18 17:49:16 -
2022-09-15 23:33:28
-
2022-09-04 21:55:56
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
