当前位置:网站首页>2704:寻找平面上的极大点
2704:寻找平面上的极大点
2022-07-31 06:25:00 【mooczhimahu】
题目
总时间限制: 1000ms内存限制: 65536kB
描述
在一个平面上,如果有两个点(x,y),(a,b),如果说(x,y)支配了(a,b),这是指x>=a,y>=b;
用图形来看就是(a,b)坐落在以(x,y)为右上角的一个无限的区域内。
给定n个点的集合,一定存在若干个点,它们不会被集合中的任何一点所支配,这些点叫做极大值点。
编程找出所有的极大点,按照x坐标由小到大,输出极大点的坐标。
本题规定:n不超过100,并且不考虑点的坐标为负数的情况。
输入
输入包括两行,第一行是正整数n,表示是点数,第二行包含n个点的坐标,坐标值都是整数,坐标范围从0到100,输入数据中不存在坐标相同的点。
输出
按x轴坐标最小到大的顺序输出所有极大点。
输出格式为:(x1,y1),(x2,y2),...(xk,yk)
注意:输出的每个点之间有","分隔,最后一个点之后没有",",少输出和多输出都会被判错
样例输入
5 1 2 2 2 3 1 2 3 1 4
样例输出
(1,4),(2,3),(3,1)
首先打好程序框架,定义变量。
其中a用来储存输入,b储存结果,n为点数,i和j用来循环,t用来判断"极大点",m用来累加储存b
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x,y;
}a[105],b[105];
int main()
{
int m=0,t,i,j,n;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
}
接下来双for判断,判断某个点是否被支配,如果循环结束,t为1,说明"只有自己才能支配自己"。
这时,把"极大点"储存到b中。
for(i=1;i<=n;i++)
{
t=0;
for(j=1;j<=n;j++)
if(a[j].x>=a[i].x&&a[j].y>=a[i].y)
t++;
if(t==1)
{
b[++m].x=a[i].x;
b[m].y=a[i].y;
}
}
最后给b排序,可参见:
sort(快速排列)的使用方法_mooczhimahu的博客-CSDN博客
排列后输出就可以了。
sort(b+1,b+1+m,cmp);
printf("(%d,%d)",b[1].x,b[1].y);
for(i=2;i<=m;i++)
printf(",(%d,%d)",b[i].x,b[i].y);
易错点
1.输出时数据之间有逗号,需要格外注意。
2.快排(快速排列)时,排列长度是m,而不是n。
3.因为有多组数据,t要初始化。
完整程序
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x,y;
}a[105],b[105];
bool cmp(node a,node b)
{
return a.x<b.x;
}
int main()
{
int m=0,t,i,j,n;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
for(i=1;i<=n;i++)
{
t=0;
for(j=1;j<=n;j++)
if(a[j].x>=a[i].x&&a[j].y>=a[i].y)
t++;
if(t==1)
{
b[++m].x=a[i].x;
b[m].y=a[i].y;
}
}
sort(b+1,b+1+m,cmp);
printf("(%d,%d)",b[1].x,b[1].y);
for(i=2;i<=m;i++)
printf(",(%d,%d)",b[i].x,b[i].y);
}
边栏推荐
猜你喜欢
毫米波技术基础
【第四章】详解Feign的实现原理
【面试:并发篇38:多线程:线程池】ThreadPoolExecutor类的基本概念
高并发与多线程之间的难点对比(容易混淆)
2022.07.14_Daily Question
‘vite‘ 不是内部或外部命令,也不是可运行的程序 或批处理文件。
Conditional statements of shell (test, if, case)
【网络攻防】常见的网络攻防技术——黑客攻防(通俗易懂版)
LeetCode:952. 按公因数计算最大组件大小【欧拉筛 + 并查集】
Core Tower Electronics won the championship in the Wuhu Division of the 11th China Innovation and Entrepreneurship Competition
随机推荐
Titanic 预测问题
2022.07.26_每日一题
零样本学习&Domain-aware Visual Bias Eliminating for Generalized Zero-Shot Learning
【Go语言刷题篇】Go完结篇函数、结构体、接口、错误入门学习
文件 - 05 下载文件:根据文件Id下载文件
《白帽子说Web安全》思维导图
Zabbix6.2 Surprise Release!Especially optimize the performance of medium and large environment deployment!
2022.07.18 _ a day
2022.07.12_每日一题
SQLite数据库连接字符串
线程唤醒机制
【Go语言入门教程】Go语言简介
Postgresql source code learning (34) - transaction log ⑩ - full page write mechanism
ros小乌龟画图
Jobject 使用
DAY18: Xss Range Clearance Manual
小实战项目之——吃货联盟订餐系统
nohup principle
iOS大厂面试查漏补缺
知识、创新、回报。