This article is made by Jason-Cow.

Welcome to reprint.

But please post the article's address.

 

 

 

核心思想

　　1.积角排序

　　2.双端队列维护半平面交

木有啦～～

1 int HPI(L*l,int n,D*ans){ 2   int head,tail,m=0;D*P=new D[n];L*q=new L[n]; 3   sort(l+1,l+n+1),q[head=tail=0]=l[1]; 4   for(int i=2;i<=n;i++){ 5     while(head
     
       8     if(fabs(Cross(q[tail].v,q[tail-1].v))
     

多边形相关

db Area(D*R,int n){    db S=0.0;    for(int i=1;i

 

 

主程序

1 L l[500];D A[500]; 2 int main(){ 3   for(int n;scanf("%d",&n)&&n;){ 4     for(int i=1;i<=n;i++){ 5       db a,b,c,d; 6       scanf("%lf%lf%lf%lf",&a,&b,&c,&d); 7       D A(a,b),B(c,d); 8       l[i]=L(A,B-A); 9     }10     int m=HPI(l,n,A);11     cout<<"m="<
     
      <
     

 

 

读入，如图（橙、红、蓝、绿）

42 1 1 21 2 0 11 0 2 10 1 1 0

输出

m=4(0.0000,1.0000)(1.0000,0.0000)(2.0000,1.0000)(1.0000,2.0000)S=2.00C=5.66

读入

 

61 2 0 10 1.8 0.8 0.20 1 1 01 0 2 13 0 1 20.6 1.6 0 0.7

 

输出

m=6(0.6000,1.6000)(0.3143,1.1714)(0.8000,0.2000)(1.0000,0.0000)(2.0000,1.0000)(1.0000,2.0000)S=1.76C=5.28

完整代码

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include