LightOJ 1285 - Drawing Simple Polygon （几何，极角排序）

阅读量：5742 次

发布时间：2019-06-18

本文共 3587 字，大约阅读时间需要 11 分钟。

1285 - Drawing Simple Polygon

Time Limit: 2 second(s)

Memory Limit: 32 MB

Given set of points in the plane, your task is to draw a polygon using the points. You have to use all the points. To be more specific, each point of the set has to be a vertex of the polygon, and the polygon must not have any other vertices. No two line segments of the polygon may have any point in common, except for the middle vertex of two consecutive line segments. For example, given the points on the left-hand side, a valid polygon is shown on the right-hand side:

You can assume that, no two points will share the same location.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (3 ≤ n ≤ 2000), denoting the number of points. The next line contains the co-ordinates of the points. Each point is specified by two integer x y in the range [-10⁴, 10⁴].

Output

For each case, print the case number in a single line first. In the next line print 'Impossible' if no solution can be found. Otherwise print a permutation of the numbers 0 to n-1. Each of these numbers represents the index of a point, in the same order as given in the input. When drawing line segments between consecutive points in the order given by this permutation, the result must be a valid polygon. Insert a single space between two integers.

Sample Input

Output for Sample Input

0 0 2 0 0 1 1 0

0 0 10 0 10 5 5 -1 0 5

Case 1:

0 3 1 2

Case 2:

2 1 3 0 4

Note

This is a special judge problem; wrong output format may cause 'wrong answer'.

PROBLEM SETTER: SABBIR YOUSUF SANNY

SPECIAL THANKS: JANE ALAM JAN (DESCRIPTION, SOLUTION, DATASET)

题意：

给了n个点，让连成一个多边行。

按照极角排序下，然后搞，就是最好一个点共线的要倒序下。

注意极角排序，第一个点不要排（坑了好久，第一个点排了可能会有问题的）

1 /* ***********************************************  2 Author        :kuangbin  3 Created Time  :2014/4/22 17:41:27  4 File Name     :E:\2014ACM\专题学习\计算几何\凸包\LightOJ1285.cpp  5 ************************************************ */  6   7 #include 
     
        8 #include 
      
         9 #include 
       
         10 #include 
        
          11 #include 
         
           12 #include 
          
            13 #include 
           
             14 #include 
             15 #include 
             
               16 #include 
              
                17 #include 
               
                 18 #include 
                
                  19 using namespace std; 20 const int maxp = 2010; 21 struct Point 22 { 23 int x,y; 24 int index; 25 Point(){} 26 Point(int _x,int _y) 27 { 28 x = _x; 29 y = _y; 30 } 31 void input() 32 { 33 scanf("%d%d",&x,&y); 34 } 35 bool operator < (Point b)const 36 { 37 return x == b.x ? y < b.y:x < b.x; 38 } 39 Point operator - (const Point &b)const 40 { 41 return Point(x-b.x,y-b.y); 42 } 43 int operator ^(const Point &b)const 44 { 45 return x*b.y - y*b.x; 46 } 47 int len2() 48 { 49 return x*x + y*y; 50 } 51 }; 52 Point p[maxp]; 53 bool cmp(Point a,Point b) 54 { 55 int tt = (a-p[0])^(b-p[0]); 56 if(tt == 0) 57 return (a-p[0]).len2() < (b-p[0]).len2(); 58 else return tt > 0; 59 } 60 61 int main() 62 { 63 //freopen("in.txt","r",stdin); 64 //freopen("out.txt","w",stdout); 65 int T; 66 int n; 67 scanf("%d",&T); 68 int iCase = 0; 69 while(T--) 70 { 71 iCase++; 72 scanf("%d",&n); 73 for(int i = 0;i < n;i++) 74 { 75 p[i].input(); 76 p[i].index = i; 77 } 78 sort(p,p+n); 79 sort(p+1,p+n,cmp); 80 int tmp = 0; 81 for(int i = n-2;i > 0;i--) 82 if(( (p[n-1]-p[0])^(p[i]-p[0]) ) != 0) 83 { 84 tmp = i; 85 break; 86 } 87 printf("Case %d:\n",iCase); 88 if(tmp == 0) 89 printf("Impossible\n"); 90 else 91 { 92 reverse(p+tmp+1,p+n); 93 for(int i = 0;i < n;i++) 94 { 95 printf("%d",p[i].index); 96 if(i < n-1)printf(" "); 97 else printf("\n"); 98 } 99 }100 }101 return 0;102 }

转载地址：http://anizx.baihongyu.com/

你可能感兴趣的文章