首页 > 代码库 > LightOj1285 - Drawing Simple Polygon(连接多边形各点)

LightOj1285 - Drawing Simple Polygon(连接多边形各点)

题目链接:http://lightoj.com/volume_showproblem.php?problem=1285

题意:给你一些点,然后把它们用一条线把它们连起来,构成一个多边形,不能有相交,必须用完所有的点,如果不能构成输出Impossible;

不能构成就是所有的点在一条直线上的时候;先按极角进行排序,然后倒着找到一个不再起点到终点那条线上的点,倒着连接起来;

技术分享
#include <stdio.h>#include <algorithm>#include <cstring>#include <cmath>using namespace std;const int N = 2010;const double eps = 1e-6;const double PI = acos(-1);struct point{    double x, y;    int Id;    point(){}    point(double x, double y) : x(x), y(y) {}    point friend operator - (const point &p1, const point &p2)///矢量p2p1;    {        return point(p1.x-p2.x, p1.y-p2.y);    }    double friend operator ^ (const point &p1, const point &p2)///p1×p2;    {        return p1.x*p2.y - p1.y*p2.x;    }};point p[N];double Dist(point p1, point p2){    double dx = p1.x - p2.x, dy = p1.y - p2.y;    return sqrt(dx*dx + dy*dy);}int cmp1(point p1, point p2)///位置排序,找到最下方的;{    if(p1.y != p2.y)        return p1.y < p2.y;    return p1.x < p2.x;///若有多个下方的找左边的;}int cmp2(point p1, point p2)///极角排序;若极角相同,距离近的在前面;{    double k = (p1-p[0])^(p2-p[0]);    if( k>eps || (fabs(k)<eps && Dist(p1, p[0]) < Dist(p2, p[0]) ))        return 1;    return 0;}int main(){    int n, T, t=1;    scanf("%d", &T);    while(T--)    {        scanf("%d", &n);        for(int i=0; i<n; i++)        {            scanf("%lf %lf", &p[i].x, &p[i].y);            p[i].Id = i;        }        sort(p, p+n, cmp1);///p[0]为最下方靠左的点;        sort(p+1, p+n, cmp2);///以p[0]为基点,按叉积进行排序;        int flag = 0;        for(int i=n-2; i>0; i--)        {            if(((p[n-1]-p[0])^(p[i]-p[0]))!=0)            {                flag = i;                break;            }        }        printf("Case %d:\n", t++);        if(flag==0)        {            printf("Impossible\n");            continue;        }        reverse(p+flag+1, p+n);        for(int i=0; i<n; i++)            printf("%d%c", p[i].Id, i==n-1?\n: );    }    return 0;}
View Code

 

LightOj1285 - Drawing Simple Polygon(连接多边形各点)