题意：
一个凸多边形的边界上有若干木桩，现丢失部分木桩，问由剩下的木桩能否唯一确定这个多边形
解法：
首先能够唯一确定的条件是由剩下的木桩确定的凸包的每条边上至少包含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