題意：
一個(gè)凸多邊形的邊界上有若干木樁，現(xiàn)丟失部分木樁，問(wèn)由剩下的木樁能否唯一確定這個(gè)多邊形
解法：
首先能夠唯一確定的條件是由剩下的木樁確定的凸包的每條邊上至少包含3個(gè)木樁，這個(gè)自己畫圖比劃下就知道了- -
然后就是求一個(gè)凸包了。在這種坐標(biāo)都是整數(shù)的情況下，凸包最好不要用atan2函數(shù)，而是用叉積來(lái)比較。我特地用純C寫了個(gè)，有要的童鞋可以拿去當(dāng)模板
有個(gè)陰險(xiǎn)的地方，就是測(cè)試數(shù)據(jù)只有3個(gè)點(diǎn)，而且3點(diǎn)一線。。。你懂的
代碼
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