1230：尋找平面上的極大點(diǎn)

時(shí)間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 4853 ??? 通過數(shù): 2625

【題目描述】

在一個(gè)平面上，如果有兩個(gè)點(diǎn)(x,y)，(a,b)，如果說(x,y)支配了(a,b)，這是指x≥a，y≥b;

用圖形來看就是(a,b)坐落在以(x,y)為右上角的一個(gè)無限的區(qū)域內(nèi)。

給定n個(gè)點(diǎn)的集合，一定存在若干個(gè)點(diǎn)，它們不會被集合中的任何一點(diǎn)所支配，這些點(diǎn)叫做極大值點(diǎn)。

編程找出所有的極大點(diǎn)，按照x坐標(biāo)由小到大，輸出極大點(diǎn)的坐標(biāo)。

本題規(guī)定：n不超過100，并且不考慮點(diǎn)的坐標(biāo)為負(fù)數(shù)的情況。

【輸入】

輸入包括兩行，第一行是正整數(shù)n，表示是點(diǎn)數(shù)，第二行包含n個(gè)點(diǎn)的坐標(biāo)，坐標(biāo)值都是整數(shù)，坐標(biāo)范圍從0到100，輸入數(shù)據(jù)中不存在坐標(biāo)相同的點(diǎn)。

【輸出】

按x軸坐標(biāo)最小到大的順序輸出所有極大點(diǎn)。

輸出格式為:(x1,y1),(x2,y2),...(xk,yk)。

注意：輸出的每個(gè)點(diǎn)之間有","分隔,最后一個(gè)點(diǎn)之后沒有",",少輸出和多輸出都會被判錯(cuò)。

【輸入樣例】

5 1 2 2 2 3 1 2 3 1 4

【輸出樣例】

(1,4),(2,3),(3,1)

【提示】

【分析】

? ? ? ? 根據(jù)題意，以及樣例圖示可以看出，(1,4),(2,3),(3,1)是極大點(diǎn)，因?yàn)樵诮o定的點(diǎn)中找不出某個(gè)點(diǎn)的橫縱坐標(biāo)都大于這些點(diǎn)的坐標(biāo)值。

? ? ? ? 用貪心算法求解該題，步驟為：

? ? ? ? （1）先將給定的點(diǎn)按照x坐標(biāo)，從小到大進(jìn)行排序，如果x值相同，再按照y坐標(biāo)，從小到大排序。給定的樣例坐標(biāo)點(diǎn)，排序前為：(1,2),(2,2),(3,1),(2,3),(1,4)。排序后為：(1,2),(1,4),(2,2),(2,3),(3,1)。

? ? ? ? （2）判斷某點(diǎn)(i,j)是否為極大點(diǎn)，那么可以搜索后面的點(diǎn)的x,y是否同時(shí)大于該點(diǎn)坐標(biāo)，即x≥i && y≥j，如果存在這樣的點(diǎn)，那么(i,j)就不是極大點(diǎn)。

【參考代碼】

#include <stdio.h> #define N 110struct point {int x;int y; }a[N],t;int n;void sort() {int i,j;for(i=0;i<n-1;i++){for(j=i+1;j<n;j++){if(a[i].x > a[j].x){t=a[i];a[i]=a[j];a[j]=t;}else if(a[i].x==a[j].x && a[i].y > a[j].y){t=a[i];a[i]=a[j];a[j]=t;}}} } int main() {int i,j;int first=1; //標(biāo)記是否是第一個(gè) int found; //標(biāo)記是否能找到 scanf("%d",&n);for(i=0;i<n;i++)scanf("%d%d",&a[i].x,&a[i].y);sort();for(i=0;i<n;i++){found=1;for(j=i+1;j<n;j++){if(a[i].x <= a[j].x && a[i].y <= a[j].y){found=0;break;}}if(found){if(first){printf("(%d,%d)",a[i].x,a[i].y);first=0;}else{printf(",(%d,%d)",a[i].x,a[i].y);}} }printf("\n");return 0; }

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

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通（1230：寻找平面上的极大点）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。