尋找平面上的極大點

鏈接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1230

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB

【題目描述】

在一個平面上，如果有兩個點(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)

【提示】

提示:

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; struct node{int x,y,f; }; node p[105]; bool cmp(node A,node B) {if(A.x==B.x)return A.y<B.y;return A.x<B.x; } int main() {int n;cin>>n;for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;sort(p+1,p+1+n,cmp);for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(p[j].y>=p[i].y){p[i].f=1;break;}int i=1;while(p[i].f)i++;printf("(%d,%d)",p[i].x,p[i].y);i++;for(;i<=n;i++)if(!p[i].f)printf(",(%d,%d)",p[i].x,p[i].y);}

?

轉載于:https://www.cnblogs.com/EdSheeran/p/7750201.html

總結

以上是生活随笔為你收集整理的寻找平面上的极大点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。