当前位置: 代码迷 >> 综合 >> Hust oj 1305 多边形(数学)
  详细解决方案

Hust oj 1305 多边形(数学)

热度:87   发布时间:2023-12-22 04:52:44.0
多边形
Time Limit: 1000 MS Memory Limit: 65536 K
Total Submit: 202(84 users) Total Accepted: 110(78 users) Rating:  Special Judge: No
Description

一个封闭的多边形定义是被有限个线段包围。线段的相交点称作多边形的顶点,当你从多边形的一个顶点沿着线段行走时,最终你会回


到出发点。

凸多边形(convex)想必大家已经很熟悉了,下图给出了凸多边形和非凸多边形实例。

这里讨论的是在平面坐标的封闭凸多边形,多变形的顶点一个顶点在原点(x=0,y=0).图2显示的那样。这样的图形有两种性质。



第一种性质是多边形的顶点会在平面上少于等于三个象限,就如图二那样,第二向县里面没有多边形的点(x<0,y>0)。

为了解释第二种性质,假设你沿着多边形旅行,从原点(0,0)出发遍历每个顶点一次,当你遍历到除原点(0,0)时候,从这一点画一条和原点(0,0)的斜线。计算这种斜率。当计算完所有的斜率时候,这些斜率组成升序或降序顺序。

如图三所示。



Input

输入包含多组测试数据。

第一行输入一个整数n(50>n>0),其中n表示多边形顶点的个数,当n为0时表示结束。紧跟n行输入在平面中多边形的顶点整数x,y(-999<x,y<999),其中第一行是原点(0,0),其他的多边形顶点可能不是顺序给出。没有顶点在x,y坐标轴上,没有三个顶点共线。
Output
输出多边形的顶点,每个顶点一行,原点(0,0)首先输出。其他顶点的输出构成沿多边形(逆时针方向)构成一条旅游路线。输出格式为(x,y)如实例
Sample Input

10

0 0
70 -50
60 30
-30 -50
80 20
50 -60
90 -20
-30 -40
-10 -60
90 10
0
Sample Output
(0,0)
(-30,-40)
(-30,-50)
(-10,-60)
(50,-60)
(70,-50)
(90,-20)
(90,10)
(80,20)
(60,30)
Author

鲁学涛

说是给凸多边形的各个点排序,而且是逆时针的,那就先按象限排,再按斜率排就好咯,很简单

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2005;
struct node
{int x,y;double angle;int num;
}a[maxn];
int cmp(node A,node B)
{if(A.num==B.num)return A.angle<B.angle;elsereturn A.num<B.num;
}
int main()
{int n;while(~scanf("%d",&n)){if(n==0) break;for(int i=0;i<n;i++){scanf("%d%d",&a[i].x,&a[i].y);a[i].angle= (double)a[i].y/a[i].x  ;a[i].angle>0?a[i].angle:-a[i].angle;if(a[i].x>0 &&a[i].y>0)a[i].num=4;else if(a[i].x<0 &&a[i].y>0)a[i].num=1;else if(a[i].x<0 &&a[i].y<0)a[i].num=2;else if(a[i].x >0&&a[i].y<0)a[i].num=3;}sort(a,a+n,cmp);for(int i=0;i<n;i++){printf("(%d,%d)\n",a[i].x,a[i].y);}}return 0;
}