计算几何初步——构造凸包

 1 #include<cstdio>
 2 #include<string.h>
 3 #include<algorithm>
 4 #define N 100000
 5 #define inf 16383
 6 using namespace std;
 7 const double eps=1e-10;
 8 
 9 struct point
10 {
11     double x,y;
12 }P[N];
13 point operator -(point h1,point h2)
14 {
15     return (point){h1.x-h2.x,h1.y-h2.y};
16 }
17 long operator *(point h1,point h2)
18 {
19     return h1.x*h2.y-h1.y*h2.x;
20 }
21 
22 long sta[N],sl;
23 
24 long dis(point h1,point h2)
25 {
26     return (h1.x-h2.x)*(h1.x-h2.x)+(h1.y-h2.y)*(h1.y-h2.y);
27 }
28 
29 long chk_rig(point h1,point h2,point h3)
30 {
31     double help;
32     help=(h2-h1)*(h3-h1);
33     return (help<0);//notice:qk_sort's part contains "help==0&&dis(h1,P[1])>=dis(h2,P[1])" so there's no need to judge the situation of help==0
34 }
35 
36 bool cmp(point h1,point h2)
37 {
38     double help;
39     help=(h1-P[1])*(h2-P[1]);
40     return (help>0||help==0&&dis(h1,P[1])>=dis(h2,P[1]));
41 }
42 
43 int main()
44 {
45     long i,n,pla;
46     scanf("%ld",&n);
47     for (i=1;i<=n;i++)scanf("%lf%lf",&P[i].x,&P[i].y);
48     pla=0,P[0].y=inf;
49     for (i=1;i<=n;i++)
50         if (P[i].y<P[pla].y||P[i].y==P[pla].y&&P[i].x<P[pla].y)pla=i;
51     
52     swap(P[pla],P[1]);
53     sort(P+2,P+N+1,cmp);
54     
55     memset(sta,0,sizeof(sta));
56     sl=3;
57     sta[1]=1,sta[2]=2,sta[3]=3;
58     for (i=4;i<=n;i++){
59         while (chk_rig(P[sta[sl-1]],P[sta[sl]],P[i]))sl--;
60         sta[++sl]=i;
61     }
62     sl--;
63     
64     printf("Num of tubao:%ld\n",sl);
65     for (i=1;i<=sl;i++)printf("NO:%ld %.2lf %.2lf\n",sta[i],P[sta[i]].x,P[sta[i]].y);
66     return 0;
67 }