題意：
一個凸多邊形的邊界上有若干木樁，現丟失部分木樁，問由剩下的木樁能否唯一確定這個多邊形
解法：
首先能夠唯一確定的條件是由剩下的木樁確定的凸包的每條邊上至少包含3個木樁，這個自己畫圖比劃下就知道了- -
然后就是求一個凸包了。在這種坐標都是整數的情況下，凸包最好不要用atan2函數，而是用叉積來比較。我特地用純C寫了個，有要的童鞋可以拿去當模板
有個陰險的地方，就是測試數據只有3個點，而且3點一線。。。你懂的
代碼
1
# include <stdio.h>
2# include <stdlib.h>
3# define N 1200
4# define cross(x1,y1,x2,y2) ((x1)*(y2)-(x2)*(y1))
5# define min(a,b) ((a)<(b)?(a):(b))
6# define max(a,b) ((a)>(b)?(a):(b))
7typedef struct
8
{
9
int x,y;
10
}point;
11int n,c;
12point data[N],ans[N],std;
13int dis(point *pos)
14{
15 return (pos->x-std.x)*(pos->x-std.x)+(pos->y-std.y)*(pos->y-std.y);
16}
17int isin(point *a,point *b,point *pos)
18{
19 if(pos->x>max(a->x,b->x)||pos->x<min(a->x,b->x)||pos->y>max(a->y,b->y)||pos->y<min(a->y,b->y)) return 0;
20 else if(cross(pos->x-a->x,pos->y-a->y,b->x-a->x,b->y-a->y)!=0) return 0;
21 else return 1;
22}
23int cmp(const void *a,const void *b)
24{
25 point *aa=(point *)a,*bb=(point *)b;
26 if(cross(bb->x-std.x,bb->y-std.y,aa->x-std.x,aa->y-std.y))
27 return cross(bb->x-std.x,bb->y-std.y,aa->x-std.x,aa->y-std.y);
28 else
29 return dis(aa)-dis(bb);
30}
31void sort()
32{
33 int i;
34 int x=0xfffffff,y=0xfffffff;
35 for(i=0;i<n;i++)
36 if(data[i].y<y||data[i].y==y&&data[i].x<x)
37 y=data[i].y,x=data[i].x;
38 std.x=x;
39 std.y=y;
40 qsort(data,n,sizeof(point),cmp);
41}
42void build()
43{
44 int i;
45 c=0;
46 sort();
47 for(i=0;i<n;i++)
48
{
49 while(c>=2&&cross(data[i].x-ans[c-1].x,data[i].y-ans[c-1].y,ans[c-1].x-ans[c-2].x,ans[c-1].y-ans[c-2].y)>=0) c--;
50 ans[c++]=data[i];
51
}
52 if(c>0) ans[c++]=ans[0];
53}
54int chk()
55{
56 int i;
57 for(i=0;i<c-1;i++)
58 {
59 int count=0,j;
60 for(j=0;j<n;j++)
61 if(isin(&ans[i],&ans[i+1],&data[j]))
62 count++;
63 if(count<3) return 0;
64 }
65 return 1;
66}
67int main()
68{
69 int test;
70 scanf("%d",&test);
71 while(test--)
72 {
73 int i;
74 scanf("%d",&n);
75 for(i=0;i<n;i++)
76 scanf("%d %d",&data[i].x,&data[i].y);
77 build();
78 if(c>3&&chk()) printf("YES\n");
79 else printf("NO\n");
80 }
81 return 0;
82}
83