计算几何

POJ 2653 求最上面覆盖的线段

用一个set维护最上面的线段。删除，插入log(n)。删完set里的数后马上it++

主要是查看线段是否交。首先两个线段的矩形要相交。

然后判断一条线段的两个端点是否跨过另外一条线段所在的直线(用叉积乘积<0判断)

同理另外一条也要检查。

 1 #include <cstring>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <cmath>
 6 #include <set>
 7 using namespace std;
 8 const int Inf=0x3f3f3f3f;
 9 const double eps=1e-8;
10 int n;
11 struct Vector
12 {
13     double x,y;
14     Vector(double x=0,double y=0):x(x),y(y){}
15 }P[100100],Q[100100];
16 inline double Min(double A,double B) {return A>B?B:A;}
17 inline double Max(double A,double B) {return A>B?A:B;}
18 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
19 inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
20 inline Vector operator * (Vector A,double p) {return Vector(A.x*p,A.y*p);}
21 inline double Slope(Vector A) {if (fabs(A.x)<eps) return Inf; return A.y/A.x;}
22 inline double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
23 inline double Area2(Vector A,Vector B,Vector C) {return Cross(B-A,C-A);}
24 inline double Length(Vector A) {return sqrt(A.x*A.x+A.y*A.y);}
25 inline Vector GetLineInsersection(Vector P,Vector v,Vector Q,Vector w)
26 {
27     Vector u=P-Q;
28     double t=Cross(w,u)/Cross(v,w);
29     return P+v*t;
30 }
31 inline bool Check(Vector A,Vector B,Vector C,Vector D)
32 {
33     if (Max(A.x,B.x)<Min(C.x,D.x)) return false;
34     if (Min(A.x,B.x)>Max(C.x,D.x)) return false;
35     if (Max(A.y,B.y)<Min(C.y,D.y)) return false;
36     if (Min(A.y,B.y)>Max(C.y,D.y)) return false;
37     if (Area2(C,A,B)*Area2(D,A,B)>eps) return false;
38     if (Area2(A,C,D)*Area2(B,C,D)>eps) return false;
39     return true;
40 }
41 int main()
42 {
43     // freopen("c.in","r",stdin);
44     while (scanf("%d",&n)!=EOF)
45     {
46         if (n==0) break;
47         set<int> S;
48         for (int i=1;i<=n;i++)
49         {        
50             scanf("%lf%lf%lf%lf",&P[i].x,&P[i].y,&Q[i].x,&Q[i].y);
51             set<int>::iterator it;
52             for (it=S.begin();it!=S.end();)
53             {
54                 if (Check(P[*it],Q[*it],P[i],Q[i])) S.erase(it++);
55                 else it++;
56             }
57             S.insert(i);
58         }
59         printf("Top sticks:");
60         set<int>::iterator it=S.begin();
61         printf(" %d",*it++);
62         for (it;it!=S.end();it++) printf(", %d",*it);
63         puts(".");
64     }        
65     return 0;
66 }

C++

POJ 1556 求最短路径

同理判断叉积即可，最后用Floyd求最短路即可

 1 #include <cstdio>
 2 #include <cmath>
 3 const double eps=1e-8;
 4 const int Inf=0x3f3f3f3f;
 5 struct Vector
 6 {
 7     double x,y;
 8     Vector(double x=0,double y=0):x(x),y(y){}
 9 }P[200];
10 int n;
11 double a1,a2,b1,b2,x,f[200][200];
12 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
13 inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
14 inline Vector operator * (Vector A,double p) {return Vector(A.x*p,A.y*p);}
15 inline double Slope(Vector A) {if (fabs(A.x)<eps) return Inf; return A.y/A.x;}
16 inline double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
17 inline double Area2(Vector A,Vector B,Vector C) {return Cross(B-A,C-A);}
18 inline double Length(Vector A) {return sqrt(A.x*A.x+A.y*A.y);}
19 inline double Min(double A,double B) {return A>B?B:A;}
20 inline Vector GetLineInsersection(Vector P,Vector v,Vector Q,Vector w)
21 {
22     Vector u=P-Q;
23     double t=Cross(w,u)/Cross(v,w);
24     return P+v*t;
25 }
26 inline bool Check(int u,int v)
27 {
28     if (fabs(P[u].x-P[v].x)<eps) return false;
29     for (int i=u+1;i<=v-1;i++)
30     {
31         if (fabs(P[u].x-P[i].x)<eps || fabs(P[v].x-P[i].x)<eps) continue;
32         Vector T;
33         if (i%4==1)
34         {
35             T=Vector(P[i].x,0);
36             if (Area2(T,P[u],P[v])*Area2(P[i],P[u],P[v])<0) return false;
37         }
38         if (i%4==0)
39         {
40             T=Vector(P[i].x,10);
41             if (Area2(T,P[u],P[v])*Area2(P[i],P[u],P[v])<0) return false;
42         }
43         if (i%4==2)
44         {
45             T=Vector(P[i+1].x,P[i+1].y);
46             if (Area2(T,P[u],P[v])*Area2(P[i],P[u],P[v])<0) return false;
47         }
48     }
49     return true;
50 }
51 
52 int main()
53 {
54     // freopen("c.in","r",stdin);
55     while (scanf("%d",&n)!=EOF)
56     {
57         if (n==-1) break;
58         for (int i=0;i<n;i++)
59         {
60             scanf("%lf%lf%lf%lf%lf",&x,&a1,&b1,&a2,&b2);
61             P[i*4+1]=Vector(x,a1);
62             P[i*4+2]=Vector(x,b1);
63             P[i*4+3]=Vector(x,a2);
64             P[i*4+4]=Vector(x,b2);
65         }
66         P[0]=Vector(0,5);
67         P[n*4+1]=Vector(10,5);
68         for (int i=0;i<=4*n+1;i++)
69             for (int j=0;j<=4*n+1;j++) f[i][j]=Inf;
70         for (int i=0;i<=n*4+1;i++)
71             for (int j=i+1;j<=n*4+1;j++)
72                 if (Check(i,j))
73                     f[i][j]=f[j][i]=Length(P[i]-P[j]);
74                 
75         for (int k=0;k<=4*n+1;k++)
76             for (int i=0;i<=4*n+1;i++)
77                 for (int j=0;j<=4*n+1;j++)
78                     if (i!=j && j!=k)  f[i][j]=Min(f[i][j],f[i][k]+f[k][j]);
79         printf("%.2f
",f[0][4*n+1]);
80     }
81     return 0;
82 }

C++

POJ 1269 判断直线是否平行，共线或求交点

平行和共线slope相等，共线时有向面积为0

求交点用向量求交

 1 #include <cstdio>
 2 #include <cmath>
 3 const double eps=1e-8;
 4 const int Inf=0x3f3f3f3f;
 5 struct Vector
 6 {
 7     double x,y;
 8     Vector(double x=0,double y=0):x(x),y(y){}
 9 }P[2],Q[2];
10 int n;
11 double x,y;
12 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
13 inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
14 inline Vector operator * (Vector A,double p) {return Vector(A.x*p,A.y*p);}
15 inline double Slope(Vector A) {if (fabs(A.x)<eps) return Inf; return A.y/A.x;}
16 inline double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
17 inline double Area2(Vector A,Vector B,Vector C) {return Cross(B-A,C-A);}
18 inline Vector GetLineInsersection(Vector P,Vector v,Vector Q,Vector w)
19 {
20     Vector u=P-Q;
21     double t=Cross(w,u)/Cross(v,w);
22     return P+v*t;
23 }
24 
25 int main()
26 {
27     //freopen("c.in","r",stdin);
28     scanf("%d",&n); int nn=n;
29     puts("INTERSECTING LINES OUTPUT");
30     for (int i=1;i<=nn;i++)
31     {
32         scanf("%lf%lf",&x,&y);
33         P[1]=Vector(x,y);
34         scanf("%lf%lf",&x,&y);
35         P[2]=Vector(x,y);
36         scanf("%lf%lf",&x,&y);
37         Q[1]=Vector(x,y);
38         scanf("%lf%lf",&x,&y);
39         Q[2]=Vector(x,y);
40         if (fabs(Slope(P[2]-P[1])-Slope(Q[2]-Q[1]))<eps)
41         {
42             if (fabs(Area2(P[2],P[1],Q[1]))<eps) 
43                 puts("LINE"); else puts("NONE");
44             continue;
45         }
46         Vector W=GetLineInsersection(P[1],P[2]-P[1],Q[1],Q[2]-Q[1]);
47         printf("POINT %.2f %.2f
",W.x,W.y);
48     }
49     puts("END OF OUTPUT");
50     return 0;
51 }

C++

POJ 3304 判断是否有一条直线经过所有线段

就是枚举不同线段的两个端点。

 1 #include <cstdio>
 2 #include <cmath>
 3 const double eps=1e-8;
 4 int KASE,n;
 5 bool flag;
 6 struct Vector
 7 {
 8     double x,y;
 9     Vector (double x=0,double y=0):x(x),y(y){}
10 }a[110],b[110];
11 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
12 inline double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
13 inline double Area2(Vector A,Vector B,Vector C) {return Cross(B-A,C-A);}
14 inline bool Check(Vector A,Vector B)
15 {
16     if (fabs(A.x-B.x)<eps && fabs(A.y-B.y)<eps) return false;
17     for (int i=1;i<=n;i++)
18         if (Area2(a[i],A,B)*Area2(b[i],A,B)>eps) return false;
19     return true;
20 }
21 int main()
22 {
23     scanf("%d",&KASE);
24     for (int kase=1;kase<=KASE;kase++)
25     {
26         scanf("%d",&n);
27         for (int i=1;i<=n;i++)
28             scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&b[i].x,&b[i].y);
29         flag=false;
30         if (n<3) flag=true;
31         for (int i=1;i<=n && !flag;i++)
32             for (int j=i+1;j<=n && !flag;j++)
33             {
34                 if (Check(a[i],a[j])) flag=true;
35                 if (Check(a[i],b[j])) flag=true;
36                 if (Check(b[i],a[j])) flag=true;
37                 if (Check(b[i],b[j])) flag=true;
38             }
39         if (flag) puts("Yes!"); else puts("No!");
40     }
41     return 0;
42 }

C++

POJ 2318/2398 就每个端点在的区域

一个点在它左边的线段的叉积和它右边线段的叉积的符号相反，二分答案即可

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 const int Maxn=10000;
 6 int n,m,C[Maxn],x1,x2,y1,y2;
 7 int x,y,u,v;
 8 struct Vector
 9 {
10     int x,y;
11     Vector(int x=0,int y=0):x(x),y(y){}
12 }V[Maxn][2],P;
13 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
14 inline int Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
15 inline int Area2(Vector A,Vector B,Vector C) {return Cross(B-A,C-A);}
16 inline int Find(Vector P)
17 {
18     int l=0,r=n,ans;
19     // for (int i=0;i<n;i++)
20         // if (Area2(P,V[i+1][0],V[i+1][1])>0 && Area2(P,V[i][0],V[i+1][1])<0) return i;
21     while (true)
22     {
23         int mid=(l+r)>>1;
24         if (Area2(P,V[mid][0],V[mid][1])>0) r=mid; 
25         else l=mid;
26         if (l+1==r) break;
27     }
28     return l;
29     cout << P.x << " " << P.y << endl;;
30     for (int i=0;i<=n;i++) 
31         cout << Area2(P,V[i][1],V[i][0]) << " ";
32     cout << endl;
33     return 0;
34     // for (int i=l;i<=r;i++)
35          // if (Area2(P,V[i+1][0],V[i+1][1])>0 && Area2(P,V[i][0],V[i][1])<0) return i;
36 }
37 int main()
38 {
39     // freopen("c.in","r",stdin);
40     // freopen(")
41     while (scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2)!=EOF)
42     {
43         if (n==0) break;
44         for (int i=1;i<=n;i++)
45         {
46             scanf("%d%d",&u,&v);
47             V[i][0]=Vector(v,y2); V[i][1]=Vector(u,y1);
48         }
49         V[0][0]=Vector(x1,y2); V[0][1]=Vector(x1,y1);
50         V[++n][0]=Vector(x2,y2); V[n][1]=Vector(x2,y1);
51         memset(C,0,sizeof(C));
52         for (int i=1;i<=m;i++)
53         {
54             scanf("%d%d",&x,&y);
55             P=Vector(x,y);
56             C[Find(P)]++;
57         }
58         for(int i=0;i<n;i++)
59             printf("%d: %d
",i,C[i]);
60         printf("
");
61     }
62     return 0;
63 }

C++

POJ 2826 计算两条线段能够接水的面积，拍了一个小时没错，结果答案加了eps就A了

神数据，不是数据会出现-0.00，那种情况我特判了，WA！

首先求出判断是否相交，求出交点，交点以下就不用考虑了。

最复杂的就是一条线段会把另外一条线段覆盖住，使无法接水。

那么两条线段的上端点所构成的直线斜率一定比原来斜（看正负）

 1 #include <cstdio>
 2 #include <cmath>
 3 const double eps=1e-8;
 4 const int Inf=0x3f3f3f3f;
 5 struct Vector
 6 {
 7     double x,y;
 8     Vector(double x=0,double y=0):x(x),y(y){}
 9 }P[3],Q[3];
10 int KASE;
11 inline void Swap(Vector &A,Vector &B) {Vector T=A;A=B;B=T;}
12 inline double Min(double A,double B) {return A>B?B:A;}
13 inline double Max(double A,double B) {return A>B?A:B;}
14 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
15 inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
16 inline Vector operator * (Vector A,double p) {return Vector(A.x*p,A.y*p);}
17 inline double Slope(Vector A) {if (fabs(A.x)<eps) return Inf; return A.y/A.x;}
18 inline double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
19 inline double Area2(Vector A,Vector B,Vector C) {return Cross(B-A,C-A);}
20 inline int dcmp(double x) {if (fabs(x)<eps) return 0; return x>0?1:-1;}
21 inline double Length(Vector A) {return sqrt(A.x*A.x+A.y*A.y);}
22 inline Vector GetLineInsersection(Vector P,Vector v,Vector Q,Vector w)
23 {
24     Vector u=P-Q;
25     double t=Cross(w,u)/Cross(v,w);
26     return P+v*t;
27 }
28 inline bool Check(Vector A,Vector B,Vector C,Vector D)
29 {
30     if (Max(A.x,B.x)<Min(C.x,D.x)) return false;
31     if (Min(A.x,B.x)>Max(C.x,D.x)) return false;
32     if (Max(A.y,B.y)<Min(C.y,D.y)) return false;
33     if (Min(A.y,B.y)>Max(C.y,D.y)) return false;
34     if (Area2(C,A,B)*Area2(D,A,B)>eps) return false;
35     if (Area2(A,C,D)*Area2(B,C,D)>eps) return false;
36     return true;
37 }
38 int main()
39 {
40     // freopen("c.in","r",stdin);
41     // freopen("main.out","w",stdout);
42     scanf("%d",&KASE);
43     for (int kase=1;kase<=KASE;kase++)
44     {
45         scanf("%lf%lf%lf%lf",&P[1].x,&P[1].y,&Q[1].x,&Q[1].y);
46         scanf("%lf%lf%lf%lf",&P[2].x,&P[2].y,&Q[2].x,&Q[2].y);
47         if (dcmp(P[1].y-Q[1].y)==0) {puts("0.00");continue;}
48         if (dcmp(P[2].y-Q[2].y)==0) {puts("0.00");continue;}
49         if (dcmp(Area2(Q[2],P[1],Q[1]))==0 && dcmp(Area2(P[2],P[1],Q[1]))==0) {puts("0.00");continue;}
50         if (!Check(P[1],Q[1],P[2],Q[2])) {puts("0.00");continue;}
51         Vector I=GetLineInsersection(P[1],Q[1]-P[1],P[2],Q[2]-P[2]);
52         if (P[1].y>Q[1].y) Swap(P[1],Q[1]);
53         if (P[2].y>Q[2].y) Swap(P[2],Q[2]);
54         P[1]=P[2]=I;
55         
56         if (Slope(Q[1]-P[1])<0 && Slope(Q[2]-P[2])<0 && (Slope(Q[2]-Q[1])<Min(Slope(Q[1]-P[1]),Slope(Q[2]-P[2]))) || dcmp(Slope(Q[2]-Q[1])-Inf)==0) {puts("0.00");continue;}
57         if (Slope(Q[1]-P[1])>0 && Slope(Q[2]-P[2])>0 && (Slope(Q[2]-Q[1])>Max(Slope(Q[1]-P[1]),Slope(Q[2]-P[2]))) || dcmp(Slope(Q[2]-Q[1])-Inf)==0) {puts("0.00");continue;}
58         if (Q[1].y>Q[2].y) Swap(Q[1],Q[2]);
59         Vector E[2]; 
60         E[1].x=-10001; E[1].y=Q[1].y;
61         E[2].x=10001; E[2].y=Q[1].y;
62         I=GetLineInsersection(E[1],E[2]-E[1],P[2],Q[2]-P[2]);
63         printf("%.2f
",fabs(Area2(P[1],Q[1],I)/2.0)+eps);
64     }
65     return 0;
66 }

C++

POJ 3348 求多边形面积。

以任意一个点为源点，算有向面积更本质。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 using namespace std;
 8 const int Maxn=1010;
 9 const double Pi=3.1415926535897;
10 const double eps=1e-6;
11 struct Vector
12 {
13     double x,y;
14     Vector (double x=0,double y=0):x(x),y(y){}
15 }P[Maxn],V[Maxn];
16 int top,n,l,KASE;
17 double Ans,x,y;
18 inline void Swap(Vector &A,Vector &B) {Vector T=A;A=B;B=T;}
19 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
20 inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
21 inline double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
22 inline double Area2(Vector A,Vector B,Vector C) {return Cross(B-A,C-A);}
23 inline int dcmp(double x) {if (fabs(x)<eps) return 0; return x>0?1:-1;}
24 inline double dis(Vector A,Vector B) {return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
25 inline bool cmp(Vector A,Vector B)
26 {
27     if (dcmp(Area2(P[1],A,B))==0) return dis(A,P[1])<dis(B,P[1]);
28     return Area2(P[1],A,B)>0;
29 }
30 int main()
31 {
32     scanf("%d",&n);
33     for (int i=1;i<=n;i++)
34     {
35         scanf("%lf%lf",&x,&y);
36         P[i]=Vector(x,y);
37     }
38     if (n<=2)
39     {
40         puts("0");
41         return 0;
42     }
43     int k=1;
44     for (int i=2;i<=n;i++)
45         if (P[k].y>P[i].y || (dcmp(P[k].y-P[i].y)==0 && P[k].x>P[i].x)) k=i;
46     Swap(P[1],P[k]);
47     sort(P+2,P+n+1,cmp);
48     V[0]=P[1];V[1]=P[2]; top=1;
49     for (int i=2;i<=n;i++)
50     {
51         while (top && Area2(V[top-1],V[top],P[i])<=0) top--;
52         V[++top]=P[i];
53     }
54     if (top<=2)
55     {
56         puts("0");
57         return 0;
58     }
59     Ans=0;
60     Vector O; O=Vector(0,0);
61     for (int i=0;i<top;i++) Ans+=Area2(O,V[i],V[i+1]);
62     Ans+=Area2(O,V[top],V[0]);
63     Ans/=2.0;
64     // printf("%.2lf
",Ans);
65     printf("%d
",(int)(Ans/50.0));
66     return 0;
67         
68 }

C++

POJ 1873 暴力枚举即可。代码量还是较大的

 1 #include <cstring>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <iostream>
 6 using namespace std;
 7 const int Maxn=30;
 8 const double eps=1e-8;
 9 struct Vector
10 {
11     double x,y,v,l;
12     Vector (double x=0,double y=0):x(x),y(y){}
13 }P[Maxn],V[Maxn],B[Maxn];
14 int top,n,l,Ans;
15 double x,y,Extra_Wood;
16 inline void Swap(Vector &A,Vector &B) {Vector T=A;A=B;B=T;}
17 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
18 inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
19 inline double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
20 inline double Area2(Vector A,Vector B,Vector C) {return Cross(B-A,C-A);}
21 inline int dcmp(double x) {if (fabs(x)<eps) return 0; return x>0?1:-1;}
22 inline double dis(Vector A,Vector B) {return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
23 inline bool cmp(Vector A,Vector B)
24 {
25     if (dcmp(Area2(V[1],A,B))==0) return dis(A,V[1])<dis(B,V[1]);
26     return Area2(V[1],A,B)>0;
27 }
28 
29 inline double Get_V(int x)
30 {
31     double res=0;
32     for (int i=0;i<n;i++)
33         if (!(x&(1<<i))) res+=P[i+1].v;
34     return res;
35 }
36 inline double Get_L(int x)
37 {
38     double res=0;
39     for (int i=0;i<n;i++)
40         if (x&(1<<i)) res+=P[i+1].l;
41     return res;
42 }
43 
44 inline double Check(int x)
45 {
46     int m=0;
47     for (int i=0;i<n;i++)
48         if (!(x&(1<<i))) V[++m]=P[i+1];
49     if (m==1) return 0;
50     if (m==2) return 2*dis(V[1],V[2]);
51     int k=1;
52     for (int i=2;i<=m;i++) if (V[i].y<V[k].y || (dcmp(V[i].y-V[k].y)==0 && (V[i].x<V[k].x))) k=i;
53     Swap(V[1],V[k]);
54     sort(V+2,V+m+1,cmp);
55     int top=1;
56     B[0]=V[1]; B[1]=V[2];
57     for (int i=3;i<=m;i++)
58     {
59         while (top && (dcmp(Area2(B[top-1],B[top],V[i]))<=0)) top--;
60         B[++top]=V[i];
61     }
62     double res=0;
63     for (int i=0;i<=top;i++) res+=dis(B[i],B[i!=top?(i+1):0]);
64     return res;
65 }
66 
67 int main()
68 {
69     int KASE=0;
70     // freopen("c.in","r",stdin);
71     while (scanf("%d",&n)!=EOF)
72     {
73         if (n==0) break;
74         for (int i=1;i<=n;i++) scanf("%lf%lf%lf%lf",&P[i].x,&P[i].y,&P[i].v,&P[i].l);
75         Ans=(1<<n)-1;
76         for (int i=1;i<(1<<n)-1;i++)
77         {
78             if (Get_V(i)<Get_V(Ans)) continue;
79             double t=Check(i);
80             if (t>Get_L(i)) continue;
81             Ans=i;
82             Extra_Wood=Get_L(i)-t;
83         }
84         printf("Forest %d
",++KASE);
85         printf("Cut these trees:");
86         for (int i=0;i<n;i++)
87             if (Ans&(1<<i)) printf(" %d",i+1);
88         putchar('
');
89         printf("Extra wood: %.2lf
",Extra_Wood);
90         putchar('
');
91     }
92     return 0;
93 }

C++

POJ 2007 直接极角即可。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 using namespace std;
 8 const int Maxn=1010;
 9 const double Pi=3.1415926535897;
10 const double eps=1e-8;
11 struct Vector
12 {
13     double x,y;
14     Vector (double x=0,double y=0):x(x),y(y){}
15 }P[Maxn],V[Maxn];
16 int top,n,l;
17 double Ans,x,y;
18 inline void Swap(Vector &A,Vector &B) {Vector T=A;A=B;B=T;}
19 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
20 inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
21 inline double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
22 inline double Area2(Vector A,Vector B,Vector C) {return Cross(B-A,C-A);}
23 inline int dcmp(double x) {if (fabs(x)<eps) return 0; return x>0?1:-1;}
24 inline double dis(Vector A,Vector B) {return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
25 inline bool cmp(Vector A,Vector B)
26 {
27     if (dcmp(Area2(P[1],A,B))==0) return dis(A,P[1])<dis(B,P[1]);
28     return Area2(P[1],A,B)>0;
29 }
30 int main()
31 {
32     // freopen("c.in","r",stdin);
33     while (scanf("%lf%lf",&x,&y)!=EOF) P[++n]=Vector(x,y);
34     sort(P+2,P+n+1,cmp);
35     for (int i=1;i<=n;i++) printf("(%d,%d)
",(int)(P[i].x),(int)(P[i].y));
36     return 0;
37 }

C++

POJ 1113 求出凸包后的边长再加上圆的边长。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 using namespace std;
 8 const int Maxn=1010;
 9 const double Pi=3.1415926535897;
10 const double eps=1e-8;
11 struct Vector
12 {
13     double x,y;
14     Vector (double x=0,double y=0):x(x),y(y){}
15 }P[Maxn],V[Maxn];
16 int top,n,l;
17 double Ans,x,y;
18 inline void Swap(Vector &A,Vector &B) {Vector T=A;A=B;B=T;}
19 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
20 inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
21 inline double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
22 inline double Area2(Vector A,Vector B,Vector C) {return Cross(B-A,C-A);}
23 inline int dcmp(double x) {if (fabs(x)<eps) return 0; return x>0?1:-1;}
24 inline double dis(Vector A,Vector B) {return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
25 inline bool cmp(Vector A,Vector B)
26 {
27     if (dcmp(Area2(P[1],A,B))==0) return dis(A,P[1])<dis(B,P[1]);
28     return Area2(P[1],A,B)>0;
29 }
30 int main()
31 {
32     scanf("%d%d",&n,&l);
33     for (int i=1;i<=n;i++)
34     {
35         scanf("%lf%lf",&x,&y);
36         P[i]=Vector(x,y);
37     }
38     int k=1;
39     for (int i=2;i<=n;i++)
40         if (P[k].y>P[i].y || (dcmp(P[k].y-P[i].y)==0 && P[k].x>P[i].x)) k=i;
41     Swap(P[1],P[k]);
42     sort(P+2,P+n+1,cmp);
43     V[0]=P[1];V[1]=P[2]; top=1;
44     for (int i=2;i<=n;i++)
45     {
46         while (top && Area2(V[top-1],V[top],P[i])<=0) top--;
47         V[++top]=P[i];
48     }
49     Ans=0;
50     for (int i=0;i<=top;i++)
51         Ans+=dis(V[i],V[i!=top?(i+1):0]);
52     Ans+=2*Pi*(double)l;
53     printf("%d
",(int)(Ans+0.5));
54     return 0;
55 }

C++

POJ 3335 求多边形的核

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <algorithm>
 4 using namespace std;
 5 const int Maxn=310;
 6 const double eps=1e-8;
 7 const double Edge=10000000;
 8 struct Vector
 9 {
10     double x,y;
11     Vector (double x=0,double y=0):x(x),y(y){}
12 }a[Maxn];
13 struct Line
14 {
15     Vector a,b;
16     double angle;
17 }L[Maxn],Q[Maxn];
18 int KASE,n,tot;
19 
20 inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
21 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
22 inline Vector operator * (Vector A,double p) {return Vector(A.x*p,A.y*p);}
23 inline double operator * (Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
24 inline int dcmp(double x) {if (fabs(x)<eps) return 0; return x>0?1:-1;}
25 inline double Area2(Vector A,Vector B,Vector C) {return (B-A)*(C-A);}
26 inline Line AddLine(double x1,double y1,double x2,double y2)
27 {
28     Line T;
29     T.a.x=x1,T.a.y=y1,T.b.x=x2,T.b.y=y2;
30     T.angle=atan2(y2-y1,x2-x1);
31     return T;
32 }
33 inline Vector GLI(Vector P,Vector v,Vector Q,Vector w)
34 {
35     Vector u=P-Q;
36     double t=(w*u)/(v*w);
37     return P+v*t;
38 }
39 inline bool cmp(Line A,Line B)
40 {
41     int d=dcmp(A.angle-B.angle);
42     if (d==0) return Area2(A.a,B.a,B.b)<0;
43     return d<0;
44 }
45 inline bool Judge(Line T,Line P,Line Q)
46 {
47     Vector I=GLI(P.a,P.b-P.a,Q.a,Q.b-Q.a);
48     return Area2(I,T.a,T.b)>0;
49 }
50 bool HPI()
51 {
52     sort(L+1,L+n+1,cmp);
53     tot=1;
54     for (int i=2;i<=n;i++)
55         if (dcmp(L[i].angle-L[tot].angle)>0)
56             L[++tot]=L[i];
57     n=tot;
58     Q[0]=L[1],Q[1]=L[2];
59     int l=0,r=1;
60     for (int i=3;i<=n;i++)
61     {
62         while (r>l && Judge(L[i],Q[r],Q[r-1])) r--;
63         while (r>l && Judge(L[i],Q[l],Q[l+1])) l++;
64         Q[++r]=L[i];
65     }
66     while (r>l && Judge(Q[l],Q[r],Q[r-1])) r--;
67     while (r>l && Judge(Q[r],Q[l],Q[l+1])) l++;
68     return l+1<r;
69 }
70 
71 int main()
72 {
73     // freopen("c.in","r",stdin);
74     scanf("%d",&KASE);
75     for (int kase=1;kase<=KASE;kase++)
76     {
77         scanf("%d",&n);
78         for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
79         a[n+1]=a[1];
80         for (int i=1;i<=n;i++)
81             L[i]=AddLine(a[i].x,a[i].y,a[i+1].x,a[i+1].y);
82         // L[++n]=AddLine(-Edge,Edge,Edge,Edge);
83         // L[++n]=AddLine(Edge,Edge,Edge,-Edge);
84         // L[++n]=AddLine(Edge,-Edge,-Edge,-Edge);
85         // L[++n]=AddLine(-Edge,-Edge,-Edge,Edge);
86         if (HPI()) puts("YES"); else puts("NO");
87         // printf()
88     }
89     return 0;
90 }

C++

POJ 2451 nlogn 半平面交

  1 #include <cstdio>
  2 #include <cmath>
  3 #include <algorithm>
  4 using namespace std;
  5 const int Maxn=20100;
  6 const double eps=1e-8;
  7 const double Edge=10000;
  8 const int Inf=0x3f3f3f3f;
  9 struct Vector
 10 {
 11     double x,y;
 12     Vector (double x=0,double y=0):x(x),y(y){}
 13 }P[Maxn];
 14 struct Line
 15 {
 16     Vector a,b;
 17     double angle;
 18 }L[Maxn],Q[Maxn];
 19 int n,ret;
 20 inline void Swap(Vector &A,Vector &B) {Vector T=A;A=B;B=T;}
 21 inline double Min(double A,double B) {return A>B?B:A;}
 22 inline double Max(double A,double B) {return A>B?A:B;}
 23 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
 24 inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
 25 inline Vector operator * (Vector A,double p) {return Vector(A.x*p,A.y*p);}
 26 inline double Slope(Vector A) {if (fabs(A.x)<eps) return Inf; return A.y/A.x;}
 27 inline double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
 28 inline double Area2(Vector A,Vector B,Vector C) {return Cross(B-A,C-A);}
 29 inline int dcmp(double x) {if (fabs(x)<eps) return 0; return x>0?1:-1;}
 30 inline double Length(Vector A) {return sqrt(A.x*A.x+A.y*A.y);}
 31 inline Vector GetLineInsersection(Vector P,Vector v,Vector Q,Vector w)
 32 {
 33     Vector u=P-Q;
 34     double t=Cross(w,u)/Cross(v,w);
 35     return P+v*t;
 36 }
 37 inline bool cmp(const Line& A,const Line& B)
 38 {
 39     int d=dcmp(A.angle-B.angle);
 40     if (d==0)  return dcmp(Area2(A.a,B.a,B.b))>0;
 41     return d<0;
 42 }
 43 inline Line AddLine(double x1,double y1,double x2,double y2)
 44 {
 45     Line T;
 46     T.a.x=x1,T.a.y=y1,T.b.x=x2,T.b.y=y2;
 47     T.angle=atan2(y2-y1,x2-x1);
 48     return T;
 49 }
 50 inline bool Judge(Line T,Line P,Line Q)
 51 {
 52     Vector I=GetLineInsersection(P.a,P.b-P.a,Q.a,Q.b-Q.a);
 53     return dcmp(Area2(I,T.a,T.b))<0;
 54 }
 55 void HPI()
 56 {
 57     sort(L+1,L+n+1,cmp);
 58     int tot,i;
 59     for (i=2,tot=1;i<=n;i++)
 60         if (dcmp(L[i].angle-L[tot].angle)>0)
 61             L[++tot]=L[i];
 62     
 63     n=tot;
 64     Q[0]=L[1]; Q[1]=L[2];
 65     int l=0,r=1;
 66     for (int i=3;i<=n;i++)
 67     {
 68         while (r>l && Judge(L[i],Q[r],Q[r-1])) r--;
 69         while (r>l && Judge(L[i],Q[l],Q[l+1])) l++;
 70         Q[++r]=L[i];
 71     }
 72     while (r>l && Judge(Q[l],Q[r],Q[r-1])) r--;
 73     while (r>l && Judge(Q[r],Q[l],Q[l+1])) l++;
 74     Q[++r]=Q[l];
 75     ret=0;
 76     for (int i=l;i<r;i++)
 77         P[ret++]=GetLineInsersection(Q[i+1].a,Q[i+1].b-Q[i+1].a,Q[i].a,Q[i].b-Q[i].a);
 78     
 79 }
 80 inline double Get_Ans()
 81 {
 82     if (ret<3) return 0;
 83     double Ans=0;
 84     for (int i=1;i<ret-1;i++)
 85         Ans+=Area2(P[0],P[i],P[i+1]);
 86     return fabs(Ans/2.0);
 87 }
 88 int main()
 89 {
 90     double x1,x2,y1,y2;
 91     scanf("%d",&n);
 92     for (int i=1;i<=n;i++)
 93     {
 94         scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
 95         L[i]=AddLine(x1,y1,x2,y2);
 96     }
 97     L[++n]=AddLine(0,0,Edge,0);
 98     L[++n]=AddLine(Edge,0,Edge,Edge);
 99     L[++n]=AddLine(Edge,Edge,0,Edge);
100     L[++n]=AddLine(0,Edge,0,0);
101     HPI();
102     printf("%.1lf
",Get_Ans());
103     return 0;
104 }

C++

POJ 1696 极角排序

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <algorithm>
 4 using namespace std;
 5 const int Maxn=110;
 6 const double eps=1e-8;
 7 struct Vector
 8 {
 9     double x,y;
10     int id;
11     Vector (double x=0,double y=0):x(x),y(y){}
12 }P[Maxn],Ans[Maxn];
13 int KASE,n,id,pos;
14 inline void Swap(Vector &A,Vector &B) {Vector T=A;A=B;B=T;}
15 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
16 inline double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
17 inline double Area2(Vector A,Vector B,Vector C) {return Cross(B-A,C-A);}
18 inline double dcmp(double x) {if (fabs(x)<eps) return 0; return x>0?1:-1;}
19 inline double Dis(Vector A,Vector B) {return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));} 
20 inline bool cmp(Vector A,Vector B)
21 {
22     if (dcmp(Area2(P[pos],A,B))==0) return Dis(P[1],A)<Dis(P[1],B);
23     return Area2(P[pos],A,B)>0;
24 }
25 int main()
26 {
27     //freopen("c.in","r",stdin);
28     scanf("%d",&KASE);
29     for (int kase=1;kase<=KASE;kase++)
30     {
31         scanf("%d",&n);
32         for (int i=1;i<=n;i++)
33             scanf("%d%lf%lf",&id,&P[i].x,&P[i].y),P[i].id=id;
34         int k=1;
35         for (int i=2;i<=n;i++)
36             if (P[i].y<P[k].y || (dcmp(P[i].y-P[k].y)==0 && P[i].x<P[k].x))k=i;
37         Swap(P[1],P[k]);
38         Ans[1]=P[1];
39         for (int i=2;i<=n;i++)
40         {
41             pos=i-1;    sort(P+i,P+n+1,cmp);
42             Ans[i]=P[i];
43         }
44         printf("%d",n); for (int i=1;i<=n;i++) printf(" %d",Ans[i].id);
45         putchar('
');
46     }
47     return 0;
48 }

C++

POJ 3525 求多边形的最大内切圆，二分答案，向内平移的长度，当面积恰好为零时，为最大。一开始忘记看最后的输出n=0了WA了一波

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <algorithm>
  5 #include <cmath>
  6 using namespace std;
  7 const int Maxn=110;
  8 const double eps=1e-8;
  9 const double EPS=1e-15;
 10 struct Vector
 11 {
 12     double x,y;
 13     Vector(double x=0,double y=0):x(x),y(y){}
 14 }P[Maxn];
 15 struct Line
 16 {
 17     Vector a,b;
 18     double angle;
 19 }L[Maxn],Q[Maxn];
 20 inline Line AddLine(Vector A,Vector B)
 21 {
 22     Line T;
 23     T.a=A,T.b=B,T.angle=atan2(B.y-A.y,B.x-A.x);
 24     return T;
 25 }
 26 int n,nn,tot;
 27 inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
 28 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
 29 inline Vector operator * (Vector A,double p) {return Vector(A.x*p,A.y*p);}
 30 inline double operator * (Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
 31 inline double Dis(Vector T) {return sqrt(T.x*T.x+T.y*T.y);}
 32 inline int dcmp(double x) {if (fabs(x)<EPS) return 0; return x>0?1:-1;}
 33 inline double Area2(Vector A,Vector B,Vector C) {return (B-A)*(C-A);}
 34 inline Vector GLI(Vector P,Vector v,Vector Q,Vector w)
 35 {
 36     Vector u=P-Q;
 37     double t=(w*u)/(v*w);
 38     return P+v*t;
 39 }
 40 inline bool cmp(Line A,Line B)
 41 {
 42     int d=dcmp(A.angle-B.angle);
 43     if (d==0) return Area2(A.a,B.a,B.b)>=0;
 44     return d<0;
 45 }
 46 inline bool Judge(Line T,Line P,Line Q)
 47 {
 48     Vector I=GLI(P.a,P.b-P.a,Q.a,Q.b-Q.a);
 49     return Area2(I,T.a,T.b)<=0;
 50 }
 51 bool HPI()
 52 {
 53     sort(L+1,L+n+1,cmp);
 54     tot=1;
 55     for (int i=2;i<=n;i++)
 56         if (dcmp(L[i].angle-L[tot].angle)>0)
 57             L[++tot]=L[i];
 58     n=tot;
 59     Q[0]=L[1],Q[1]=L[2];
 60     int l=0,r=1;
 61     for (int i=3;i<=n;i++)
 62     {
 63         while (r>l && Judge(L[i],Q[r],Q[r-1])) r--;
 64         while (r>l && Judge(L[i],Q[l],Q[l+1])) l++;
 65         Q[++r]=L[i];
 66     }
 67     while (r>l && Judge(Q[l],Q[r],Q[r-1])) r--;
 68     while (r>l && Judge(Q[r],Q[l],Q[l+1])) l++;
 69     return l+1<r;
 70 }
 71 
 72 inline Line Move(Line T,double t)
 73 {
 74     double x=T.a.x-T.b.x;
 75     double y=T.a.y-T.b.y;
 76     double L=Dis(T.a-T.b);
 77     T.a=Vector(T.a.x+y/L*t,T.a.y-x/L*t);
 78     T.b=Vector(T.b.x+y/L*t,T.b.y-x/L*t);
 79     return T;
 80 }
 81 bool flag=false;
 82 inline void Change(double t)
 83 {
 84     n=nn;
 85     for (int i=1;i<=n;i++)
 86         L[i]=Move(AddLine(P[i],P[i+1]),t);
 87     flag=true;
 88 }
 89 inline double Work()
 90 {
 91     double l=0,r=21000;
 92     while (r-l>eps)
 93     {
 94         double mid=(l+r)/2.0;
 95         Change(mid);
 96         if (HPI()) l=mid; else r=mid; 
 97     }
 98     return l;
 99 }
100 int main()
101 {
102     // freopen("c.in","r",stdin);
103     while (scanf("%d",&n)!=EOF&&n)
104     {
105         nn=n;
106         for (int i=1;i<=n;i++) scanf("%lf%lf",&P[i].x,&P[i].y);
107         P[n+1]=P[1];
108         printf("%.10f
",Work());
109     }
110     return 0;
111 }

C++

POJ 2420 模拟退火求费马点

 1 #include <cstdio>
 2 #include <ctime>
 3 #include <cstdlib>
 4 #include <cmath>
 5 const int Point=500;
 6 const int Edge=10000;
 7 const int Mod=20000;
 8 const int Maxn=1000;
 9 const double eps=1e-8;
10 struct Vector
11 {
12     double x,y;
13     Vector (double x=0,double y=0):x(x),y(y){}
14 }P[Maxn],G[Maxn];
15 int dx[4]={0,0,-1,1};  
16 int dy[4]={-1,1,0,0}; 
17 int n,nn;
18 inline void Swap(Vector &A,Vector &B) {Vector T=A;A=B;B=T;}
19 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
20 inline Vector operator * (Vector A,double p) {return Vector(A.x*p,A.y*p);}
21 inline double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
22 inline double Area2(Vector A,Vector B,Vector C) {return Cross(B-A,C-A);}
23 inline double dcmp(double x) {if (fabs(x)<eps) return 0; return x>0?1:-1;}
24 inline double Dis(Vector A,Vector B) {return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));} 
25 inline double RAND()
26 {return (rand()%(Mod+1))*(1.0/Mod);}
27 inline double Calc(Vector u)
28 {
29     double ret=0;
30     for (int i=1;i<=n;i++) ret+=Dis(u,P[i]);
31     return ret;
32 }
33 
34 double Search()
35 {
36     double T=100;
37     Vector U=P[1];
38     while (T>eps)
39     {
40         bool flag=true;
41         while (flag)
42         {
43             flag=false;
44             for (int i=0;i<4;i++)
45             {
46                 Vector u=Vector(U.x+dx[i]*T,U.y+dy[i]*T);
47                 if (Calc(u)<Calc(U)) {U=u; flag=true;}
48             }
49         }
50         T*=0.98;
51     }
52     return Calc(U);
53 }
54 int main()
55 {
56     srand(time(0));
57     while (scanf("%d",&n)!=EOF)
58     {
59         for (int i=1;i<=n;i++) scanf("%lf%lf",&P[i].x,&P[i].y);
60         printf("%.0f",Search());
61     }
62     return 0;    
63 }

C++

POJ 3335 半平面交

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <algorithm>
 4 using namespace std;
 5 const int Maxn=310;
 6 const double eps=1e-8;
 7 const double Edge=10000000;
 8 struct Vector
 9 {
10     double x,y;
11     Vector (double x=0,double y=0):x(x),y(y){}
12 }a[Maxn];
13 struct Line
14 {
15     Vector a,b;
16     double angle;
17 }L[Maxn],Q[Maxn];
18 int KASE,n,tot;
19 
20 inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
21 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
22 inline Vector operator * (Vector A,double p) {return Vector(A.x*p,A.y*p);}
23 inline double operator * (Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
24 inline int dcmp(double x) {if (fabs(x)<eps) return 0; return x>0?1:-1;}
25 inline double Area2(Vector A,Vector B,Vector C) {return (B-A)*(C-A);}
26 inline Line AddLine(double x1,double y1,double x2,double y2)
27 {
28     Line T;
29     T.a.x=x1,T.a.y=y1,T.b.x=x2,T.b.y=y2;
30     T.angle=atan2(y2-y1,x2-x1);
31     return T;
32 }
33 inline Vector GLI(Vector P,Vector v,Vector Q,Vector w)
34 {
35     Vector u=P-Q;
36     double t=(w*u)/(v*w);
37     return P+v*t;
38 }
39 inline bool cmp(Line A,Line B)
40 {
41     int d=dcmp(A.angle-B.angle);
42     if (d==0) return Area2(A.a,B.a,B.b)<0;
43     return d<0;
44 }
45 inline bool Judge(Line T,Line P,Line Q)
46 {
47     Vector I=GLI(P.a,P.b-P.a,Q.a,Q.b-Q.a);
48     return Area2(I,T.a,T.b)>0;
49 }
50 bool HPI()
51 {
52     sort(L+1,L+n+1,cmp);
53     tot=1;
54     for (int i=2;i<=n;i++)
55         if (dcmp(L[i].angle-L[tot].angle)>0)
56             L[++tot]=L[i];
57     n=tot;
58     Q[0]=L[1],Q[1]=L[2];
59     int l=0,r=1;
60     for (int i=3;i<=n;i++)
61     {
62         while (r>l && Judge(L[i],Q[r],Q[r-1])) r--;
63         while (r>l && Judge(L[i],Q[l],Q[l+1])) l++;
64         Q[++r]=L[i];
65     }
66     while (r>l && Judge(Q[l],Q[r],Q[r-1])) r--;
67     while (r>l && Judge(Q[r],Q[l],Q[l+1])) l++;
68     return l+1<r;
69 }
70 
71 int main()
72 {
73     // freopen("c.in","r",stdin);
74     scanf("%d",&KASE);
75     for (int kase=1;kase<=KASE;kase++)
76     {
77         scanf("%d",&n);
78         for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
79         a[n+1]=a[1];
80         for (int i=1;i<=n;i++)
81             L[i]=AddLine(a[i].x,a[i].y,a[i+1].x,a[i+1].y);
82          L[++n]=AddLine(-Edge,Edge,Edge,Edge);
83          L[++n]=AddLine(Edge,Edge,Edge,-Edge);
84          L[++n]=AddLine(Edge,-Edge,-Edge,-Edge);
85          L[++n]=AddLine(-Edge,-Edge,-Edge,Edge);
86         if (HPI()) puts("YES"); else puts("NO");
87         // printf()
88     }
89     return 0;
90 }

C++

POJ 2187 最远点对，旋转卡壳调不出来

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 #include <iostream>
 6 using namespace std;
 7 const int Maxn=100100;
 8 const double eps=1e-8;
 9 struct Vector
10 {
11     double x,y;
12     Vector(double x=0,double y=0):x(x),y(y){}
13 }P[Maxn],Q[Maxn];
14 int n,top;
15 inline void Swap(Vector &x,Vector &y) {Vector T=x;x=y;y=T;}
16 inline double Max(double x,double y) {return x>y?x:y;}
17 inline double Max3(double x,double y,double z) {return Max(x,Max(y,z));}
18 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
19 inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
20 inline Vector operator * (Vector A,double p) {return Vector(A.x*p,A.y*p);}
21 inline double operator * (Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
22 inline int dcmp(double x) {if (fabs(x)<eps) return 0; return x>0?1:-1;}
23 inline double Area2(Vector A,Vector B,Vector C) {return (B-A)*(C-A);}
24 inline double Dis(Vector T) {return T.x*T.x+T.y*T.y;}
25 inline Vector GLI(Vector P,Vector v,Vector Q,Vector w)
26 {
27     Vector u=P-Q;
28     double t=(w*u)/(v*w);
29     return P+v*t;
30 }
31 bool cmp(Vector A,Vector B)
32 {
33     if (dcmp(Area2(P[1],A,B))==0) return Dis(P[1]-A)<Dis(P[1]-B);
34     return Area2(P[1],A,B)>0;
35 }
36 
37 int main()
38 {
39     scanf("%d",&n);
40     for (int i=1;i<=n;i++) scanf("%lf%lf",&P[i].x,&P[i].y);
41     int k=1;
42     for (int i=2;i<=n;i++)
43         if (P[i].y<P[k].y || (dcmp(P[i].y-P[k].y)==0 && P[i].x<P[k].x)) k=i;
44     Swap(P[1],P[k]);
45     sort(P+2,P+n+1,cmp);
46     Q[0]=P[1],Q[1]=P[2]; top=1;
47     for (int i=3;i<=n;i++)
48     {
49         if (top && Area2(P[i],Q[top],Q[top-1])>0) top--;
50         Q[++top]=P[i];
51     }
52     int j=0;
53     double Ans=0;
54     for (int i=0;i<=top;i++)
55         for (int j=0;j<=top;j++) Ans=Max(Ans,Dis(Q[i]-Q[j]));
56     printf("%d
",(int)(Ans+eps));
57     return 0;
58 }

C++

POJ 1228 判断是否为稳定凸包，判断能不能在原有凸包上加点，得到一个更大的凸包，并且这个凸包包含原有凸包上的所有点。

这道题里面我发现我的凸包写法有问题，即极角排序是若共线则按距离远近排序。最后的时候加入时，会发现最靠近的先加入然后被覆盖了就不能够全部统计了。

然而对于一般的时候还是有效的。当要求出凸包线上的点时才会有问题。数据比较弱，我写的还是比较详细的。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cmath>
 4 using namespace std;
 5 const int Maxn=4010;
 6 const double eps=1e-9;
 7 int KASE,n,top;
 8 double x,y;
 9 struct Vector
10 {
11     double x,y;
12     Vector(double x=0,double y=0):x(x),y(y){}
13 }V[Maxn],P[Maxn];
14 inline void Swap(Vector &A,Vector &B) {Vector T=A;A=B;B=T;}
15 inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
16 inline Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
17 inline double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
18 inline int dcmp(double p) {if (fabs(p)<eps) return 0; return p>0?1:-1;}
19 inline double Area2(Vector A,Vector B,Vector C) {return Cross(B-A,C-A);}
20 inline double Dis(Vector A,Vector B) {return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
21 inline bool cmp(Vector A,Vector B)
22 {
23     if (dcmp(Area2(P[1],A,B))==0) return Dis(A,P[1])<Dis(B,P[1]);
24     return Area2(P[1],A,B)>0;
25 }
26 int main()
27 {
28     scanf("%d",&KASE);
29     for (int kase=1;kase<=KASE;kase++)
30     {
31         scanf("%d",&n);
32         for (int i=1;i<=n;i++)
33         {
34             scanf("%lf%lf",&x,&y);
35             P[i]=Vector(x,y);
36         }
37         if (n<=5)
38         {
39             puts("NO");
40             continue;
41         }
42         int k=1;
43         for (int i=2;i<=n;i++) 
44             if (P[k].y>P[i].y || (dcmp(P[k].y-P[i].y)==0 || P[k].x>P[i].x)) k=i;
45         Swap(P[1],P[k]);
46         sort(P+2,P+n+1,cmp);
47         for (k=n;k>=2;k--) if (dcmp(Area2(P[1],P[k],P[k-1]))!=0) break;
48         if (k!=n)
49         {
50             Vector T=P[k];
51             for (int i=k;i<n;i++) P[i]=P[i+1];
52             P[n]=T;
53         }            
54         V[0]=P[1]; V[1]=P[2]; top=1;
55         for (int i=3;i<=n;i++)
56         {
57             while (top && dcmp(Area2(V[top-1],V[top],P[i]))<0) top--;
58             V[++top]=P[i];
59         }
60         bool flag=true;
61         for (int i=2;i<=top;i++) 
62             if (dcmp(Area2(V[0],V[i],V[i-1]))!=0) flag=false;
63         if (flag) 
64         {
65             puts("NO");
66             continue;
67         }
68         flag=true;
69         for (int i=1;i<=top-2;i++)
70             if (dcmp(Area2(V[i-1],V[i],V[i+1]))!=0 && dcmp(Area2(V[i],V[i+1],V[i+2]))!=0) {flag=false; break;}
71         if (dcmp(Area2(V[top],V[0],V[1]))!=0 && dcmp(Area2(V[0],V[1],V[2]))!=0) flag=false; //0,1
72         if (dcmp(Area2(V[top-1],V[top],V[0]))!=0 && dcmp(Area2(V[top-2],V[top-1],V[top]))!=0) flag=false;   //top,top-1
73         if (dcmp(Area2(V[top],V[0],V[1]))!=0 && dcmp(Area2(V[top],V[top-1],V[0]))!=0) flag=false; //top,0
74         if (flag) puts("YES"); else puts("NO");
75     }
76     return 0;
77 }

C++