1、凸包（最大三角形）

    1. #include <cstdio>
    2. #include <iostream>
    3. #include <cstring>
    4. #include <algorithm>
    5. #include <cmath>
    6. using namespace std;
    7. #define eps 1e-8
    8. struct node
    9. {
    10.     int x,y;
    11. };
    12. node p[50005];
    13. node res[50005];
    14. int cross(node p0,node p1,node p2)
    15. {
    16.     return (p0.x*p1.y-p1.x*p0.y)+(p1.x*p2.y-p2.x*p1.y)+(p2.x*p0.y-p0.x*p2.y);
    17. }
    18. bool cmp(node a,node b)
    19. {
    20.     if(a.x==b.x)
    21.         return a.y<b.y;
    22.     else
    23.         return a.x<b.x;
    24. }
    25. int Graham(int n)
    26. {
    27.     int len;
    28.     int top=0;
    29.     sort(p,p+n,cmp);
    30.     for(int i=0; i<n; i++)
    31.     {
    32.         while(top>1&&cross(res[top-1],p[i],res[top-2])<=0)
    33.             top--;
    34.         res[top++]=p[i];
    35.     }
    36.     len=top;
    37.     for(int i=n-2; i>=0; i--)
    38.     {
    39.         while(top>len&&cross(res[top-1],p[i],res[top-2])<=0) //如果新增的点与前两点够不成凸型，则把上一点删去
    40.             top--;
    41.         res[top++]=p[i];
    42.     }
    43.     if(n>1)
    44.         top--;
    45.     return top;
    46. }
    47. int main()
    48. {
    49.     int n;
    50.     while(cin>>n)
    51.     {
    52.         for(int i=0; i<n; i++)
    53.             cin>>p[i].x>>p[i].y;
    54.         int dian=Graham(n);
    55.         int ans=-22;
    56.         for(int i=0; i<dian; i++)
    57.             for(int j=i+1; j<dian; j++)
    58.                 for(int k=j+1; k<dian; k++)
    59.                     ans=max(ans,cross(res[j],res[k],res[i]));
    60.         printf("%.2lf\n",0.5*ans);
    61.     }
    62.     return 0;
    63. }

    2、稳定凸包

    2. struct node
    3. {
    4.     int x,y;
    5. } str[2005],res[2005];
    6. int dis(node a,node b)
    7. {
    8.     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    9. }
    11. int cross(node p1,node p2,node p3)
    12. {
    13.     return (p1.x*p2.y-p1.y*p2.x)+(p2.x*p3.y-p2.y*p3.x)+(p3.x*p1.y-p3.y*p1.x);
    14. }
    15. bool cmp(node a,node b)
    16. {
    17.     if(cross(str[0],a,b)>0) return 1;//不共线
    18.     else if(cross(str[0],a,b)==0&&dis(str[0],a)<dis(str[0],b)) return 1;//共线选距离短的
    19.     return 0;
    20. }
    21. void tubao(int n)
    22. {
    23.     int top=1;
    24.     sort(str,str+n,cmp1);
    25.     res[0]=str[0];res[1]=str[1];
    26.     for(int i=2;i<n;i++){
    27.         while(top && cross(str[i],res[top],res[top-1])>0)top--;
    28.         res[++top]=str[i];
    29.     }
    30.     int len=top;
    31.     res[++top]=str[n-2];
    32.     for(int i=n-3;i>=0;i--){
    33.         while(top!=len &&cross(str[i],res[top],res[top-1])>0)top--;
    34.         res[++top]=str[i];
    35.     }
    36.     return --top;}
    38. int judge()
    39. {
    40.     for(int i=1; i<top; i++)
    41.         if(cross(arr[i],arr[i-1],arr[i+1])!=0&&cross(arr[i],arr[i+2],arr[i+1])!=0) return 0;//判断三点共线
    42.     return 1;
    43. }
    44. int main()
    45. {
    46.     int n,m;
    47.     int t;
    48.     cin>>t;
    49.     while(t--)
    50.     {
    51.         cin>>n;
    52.         for(int i=0; i<n; i++)
    53.         {
    54.             cin>>str[i].x>>str[i].y;
    55.         }
    56.         int pos=0;
    57.         for(int i=1; i<n; i++)
    58.         {
    59.             if((str[i].x<str[pos].x)||(str[i].x==str[pos].x&&str[i].y<str[pos].y))//选出最优顶点
    60.                 pos=i;
    61.         }
    62.         swap(str[0],str[pos]);
    63.         tubao(n);
    64.         if(judge()&&n>=6)
    65.             cout<<"YES"<<endl; 
    66.         else
    67.             cout<<"NO"<<endl;
    68.     }
    69.     return 0;
    70. }

    3、pick定理

    1. //在网格中计算两点连线上的点个数：gcd(abs(x1-x2),abs(y1-y2));
    2. //Pick定理：s=in+out/2-1;
    3. struct node
    4. {
    5.     int x,y;
    6. } str[105];
    7. int gcd(int n,int m)
    8. {
    9.     if(m==0)
    10.         return n;
    11.     else
    12.         return gcd(m,n%m);
    13. }
    14. int cross(node p1,node p2)
    15. {
    16.     return p1.x*p2.y-p1.y*p2.x;
    17. }
    18. int main()
    19. {
    20.     int flag=1;
    21.     int t;
    22.     int m;
    23.     cin>>t;
    24.     while(t--)
    25.     {
    26.         cin>>m;
    27.         int x,y;
    28.         str[0].x=0,str[0].y=0;
    29.         for(int i=1; i<=m; i++)
    30.         {
    31.             cin>>x>>y;
    32.             str[i].x=str[i-1].x+x;
    33.             str[i].y=str[i-1].y+y;
    34.         }
    35.         int area=0;
    36.         int out=0;
    37.         int in=0;
    38.         for(int i=1; i<m; i++)
    39.         {
    40.             area+=cross(str[i],str[i+1]);//差积计算面积 
    41.             out+=gcd(abs(str[i].x-str[i+1].x),abs(str[i].y-str[i+1].y));
    42.         }
    43.         area += cross(str[m], str[1]);
    44.         out += gcd(abs(str[m].x - str[1].x), abs(str[m].y - str[1].y));
    45.         if(area<0)
    46.             area=-area;
    48.         in=area+2-out;
    49.         in/=2;
    50.         cout<<"Scenario #"<<flag++<<":"<<endl;
    51.         if(area%2==0)
    52.         {
    53.             printf("%d %d %d.0\n\n",in,out,area/2);
    54.         }
    55.         else
    56.         {
    57.             printf("%d %d %d.5\n\n",in,out,area/2);
    58.         }
    59.     }
    60.     return 0;
    61. }

    4、旋转卡壳算法

    1. const int maxl=2000+10;
    2. struct node
    3. {
    4.     double x,y;
    5. }str[maxl],res[maxl];
    6. double dis(node a,node b)
    7. {
    8.     return (double)sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    9. }
    10. bool cmp(node a,node b)
    11. {
    12.     if(a.x==b.x)
    13.         return a.y<b.y;
    14.     return a.x<b.x;
    15. }
    16. double cross(node a,node b,node c)
    17. {
    18.     return (a.x*b.y-a.y*b.x)+(b.x*c.y-b.y*c.x)+(c.x*a.y-c.y*a.x);
    19. }
    20. int tubao(int n) 
    21. { 
    22.     sort(str,str+n,cmp);
    23.     int len;
    24.     int top=0;
    25.     for(int i=0;i<n;i++)
    26.     {
    27.         while(top>1&&cross(res[top-1],str[i],res[top-2])<=0)
    28.             top--;
    29.         res[top++]=str[i];
    30.     }
    31.     len=top;
    32.     for(int i=n-2;i>=0;i--)
    33.     {
    34.         while(top>len&&cross(res[top-1],str[i],res[top-2])<=0)
    35.             top--;
    36.         res[top++]=str[i];
    37.     }
    38.     if(n>1)
    39.         top--;
    40.     return top;
    41. }
    42. int main()
    43. {
    44.     int n;
    45.     scanf("%d",&n);
    46.     for(int i=0;i<n;i++)
    47.     {
    48.         scanf("%lf%lf",&str[i].x,&str[i].y);
    49.     }
    50.     int ans=tubao(n);
    51.     double sum=0;
    52.     for(int i=0;i<ans-2;i++)
    53.     {
    54.         int ti=(i+3)%ans,tj=(i+1)%ans;
    55.         for(int j=i+2;j<ans;j++)
    56.         {
    57.             //对角线两边选一个点计算面积
    58.             while(fabs(cross(res[i],res[j],res[ti]))<fabs(cross(res[i],res[j],res[(ti+1)%ans]))) ti=(ti+1)%ans;
    59.             while(fabs(cross(res[i],res[j],res[tj])) < fabs(cross(res[i],res[j],res[(tj+1)%ans]))) tj=(tj+1)%ans;
    60.             sum = max(sum, fabs(cross(res[i],res[j],res[ti]))+fabs(cross(res[i],res[j],res[tj])));//计算四边形最大面积
    61.         }
    62.     }
    63.     printf("%.3lf\n",sum/2);
    64.     return 0;
    65. }
    68. //输入信息
    69. int ans=tubao(n);
    70. int sum=0;
    71. int q=1;
    72. res[ans]=res[0];
    73. for(int p=0; p<ans; p++)
    74. {
    75.     while(cross(res[p+1],res[q],res[p])<cross(res[p+1],res[q+1],res[p]))
    76.         q=(q+1)%ans;
    77.     sum=max(sum,max(dis(res[p],res[q]),dis(res[p+1],res[q+1])));
    78. }
    79. printf("%d\n",sum);
    80. 3、（分治）计算最短距离点对(nlogn)
    81.     const int maxl=100000+10;
    82. const double inf=1e20;
    83. struct node
    84. {
    85.     double x,y;
    86. } str[maxl],arr[maxl];
    87. double dist(node a,node b)
    88. {
    89.     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    90. }
    91. //利用排序规则将点分为左右两部分
    92. bool cmp(node a,node b)
    93. {
    94.     if(a.x==b.x)
    95.         return a.y<b.y;
    96.     return a.x<b.x;
    97. }
    98. //把以中线为界左右一定范围的点进行排序
    99. bool cmp1(node a,node b)
    100. {
    101.     return a.y<b.y;
    102. }
    103. double clost(int left,int right)
    104. {
    105.     double d=inf;
    106.     if(left==right)
    107.     {
    108.         return d;
    109.     }
    110.     if(left+1==right)
    111.     {
    112.         return dist(str[left],str[right]);
    113.     }
    114.     int mid=(left+right)/2;
    115.     double d1=clost(left,mid);//再分为左边界
    116.     double d2=clost(mid+1,right);//分为右边界
    117.     d=min(d1,d2);//取两边界最小
    118.     int k=0;
    119.     //将分界线周围符合要求的点记录起来
    120.     for(int i=left; i<=right; i++)
    121.     {
    122.         if(fabs(str[mid].x-str[i].x)<=d)
    123.         {
    124.             arr[k++]=str[i];
    125.         }
    126.     }
    127.     sort(arr,arr+k,cmp1);
    128.     //对分界线周围符合条件的点进行处理，更新d
    129.     for(int i=0; i<k; i++)
    130.     {
    131.         for(int j=i+1; j<k&&arr[j].y-arr[i].y<d; j++)
    132.         {
    133.             d=min(d,dist(arr[i],arr[j]));
    134.         }
    135.     }
    136.     return d;
    137. }
    138. int main()
    139. {
    140.     int n;
    141.     while(cin>>n&&n)
    142.     {
    143.         for(int i=0; i<n; i++)
    144.         {
    145.             cin>>str[i].x>>str[i].y;
    146.         }
    147.         sort(str,str+n,cmp);
    148.         printf("%.2lf\n",clost(0,n-1)/2);
    149.     }
    150.     return 0;
    151. }

    5、半平面交

    1. //in the counterclockwise order：逆时针
    2. //in clockwise order：顺时针
    4. //(多边形的核)
    5. #define exp 1e-8
    6. const int maxl = 210;
    7. int ccnt, zcnt;//ccnt为最终切割后得到多边形的顶点个数，zcnt暂存
    8. int m;
    9. struct point
    10. {
    11.     double x, y;
    12. };
    13. point arr[maxl], p[maxl], q[maxl];
    14. void getline(point x, point y, double &a, double &b, double   &c) //两点x、y确定一条直线a、b、c为其系数
    15. {
    16.     a = y.y - x.y;
    17.     b = x.x - y.x;
    18.     c = y.x * x.y - x.x * y.y;
    19. }
    20. void initial()
    21. {
    22.     for (int i = 1; i <= m; ++i)p[i] = arr[i];
    23.     p[m + 1] = p[1];
    24.     p[0] = p[m];
    25.     ccnt = m;//ccnt为最终切割得到的多边形的顶点数，将其初始化为多边形的顶点的个数
    26. }
    27. point jiaodian(point x, point y, double a, double b, double c) //求x、y形成的直线与已知直线a、b、c、的交点
    28. {
    29.     double u = fabs(a * x.x + b * x.y + c);
    30.     double v = fabs(a * y.x + b * y.y + c);
    31.     point pt;
    32.     pt.x = (x.x * v + y.x * u) / (u + v);
    33.     pt.y = (x.y * v + y.y * u) / (u + v);
    34.     return  pt;
    35. }
    36. void cut(double a, double b, double c)
    37. {
    38.     zcnt = 0;
    39.     for (int i = 1; i <= ccnt; ++i)
    40.     {
    41.         if (a*p[i].x + b * p[i].y + c >= 0)q[++zcnt] = p[i];// c由于精度问题，可能会偏小，所以有些点本应在右侧而没在，
    42.         //故应该接着判断
    43.         else
    44.         {
    45.             if (a*p[i - 1].x + b * p[i - 1].y + c > 0) //如果p[i-1]在直线的右侧的话，
    46.             {
    47.                 //则将p[i],p[i-1]形成的直线与已知直线的交点作为核的一个顶点(这样的话，由于精度的问题，核的面积可能会有所减少)
    48.                 q[++zcnt] = jiaodian(p[i], p[i - 1], a, b, c);
    49.             }
    50.             if (a*p[i + 1].x + b * p[i + 1].y + c > 0) //原理同上
    51.             {
    52.                 q[++zcnt] = jiaodian(p[i], p[i + 1], a, b, c);
    53.             }
    54.         }
    55.     }
    56.     for (int i = 1; i <= zcnt; ++i)p[i] = q[i];//将q中暂存的核的顶点转移到p中
    57.     p[zcnt + 1] = q[1];
    58.     p[0] = p[zcnt];
    59.     ccnt = zcnt;
    60. }
    61. //判断面积大小
    62. int dcmp(double x)
    63. {
    64.     if (fabs(x) < exp) return 0;
    65.     else return 1;
    66. }
    67. void solve()
    68. {
    69.     //注意：默认点是顺时针，如果题目不是顺时针，规整化方向
    70.     initial();
    71.     for (int i = 1; i <= m; ++i)
    72.     {
    73.         double a, b, c;
    74.         getline(arr[i], arr[i + 1], a, b, c);
    75.         cut(a, b, c);
    76.     }
    77.     //多边形核的面积
    78.     double area = 0;
    79.     for (int i = 1; i <= zcnt; ++i)
    80.         area += p[i].x * p[i + 1].y - p[i + 1].x * p[i].y;
    81.     area = fabs(area / 2.0);
    82.     //面积为0，不存在核点
    83.     if (!zcnt&&dcmp(area) == 0)
    84.         puts("NO");
    85.     else
    86.         puts("YES");
    88. }
    89. //如果输入点是顺时针则不用，如果是逆时针，则将点的方向发过来
    90. void GuiZhengHua(){
    91.     //规整化方向，逆时针变顺时针，顺时针变逆时针
    92.     for(int i = 1; i < (m+1)/2; i ++)
    93.         swap(arr[i], arr[m-i]);
    94. }
    95. int main()
    96. {
    97.     int t;
    98.     cin >> t;
    99.     while (t--)
    100.     {
    101.         cin >> m;
    102.         int i;
    103.         for (i = 1; i <= m; i++)
    104.             cin >> arr[i].x >> arr[i].y;
    105.         arr[m + 1] = arr[1];
    106.         solve();
    107.     }
    108.     return 0;
    109. }
    112. //求多边形中最大圆半径
    113. #include<iostream>
    114. #include<string.h>
    115. #include<algorithm>
    116. #include<cmath>
    117. #include<stdio.h>
    118. using namespace std;
    119. const int maxn=210;
    120. const double esp=1e-8;
    121. const int inf=1e9;
    122. int ccnt,zcnt;
    123. int m;
    124. struct node
    125. {
    126.     double x,y;
    127. };
    128. node arr[maxn],p[maxn],q[maxn];
    129. void GetLine(node x,node y,double &a,double &b,double &c)
    130. {
    131.     a=y.y-x.y;
    132.     b=x.x-y.x;
    133.     c=y.x*x.y-x.x*y.y;
    134. }
    136. void initial()
    137. {
    138.     for(int i=1; i<=m; i++) p[i]=arr[i];
    139.     p[m+1]=p[1];
    140.     p[0]=p[m];
    141.     ccnt=m;
    142. }
    144. node jiaodian(node x,node y,double a,double b,double c)
    145. {
    146.     double u=fabs(a*x.x+b*x.y+c);
    147.     double v=fabs(a*y.x+b*y.y+c);
    148.     node pt;
    149.     pt.x=(x.x*v+y.x*u)/(u+v);
    150.     pt.y=(x.y*v+y.y*u)/(u+v);
    151.     return pt;
    152. }
    154. void cut(double a,double b,double c)
    155. {
    156.     zcnt=0;
    157.     for(int i=1; i<=ccnt; i++)
    158.     {
    159.         if(a*p[i].x+b*p[i].y+c>=0) q[++zcnt]=p[i];
    160.         else
    161.         {
    162.             if(a*p[i-1].x+b*p[i-1].y+c>0)
    163.             {
    164.                 q[++zcnt]=jiaodian(p[i],p[i-1],a,b,c);
    165.             }
    166.             if(a*p[i+1].x+b*p[i+1].y+c>0)
    167.             {
    169.                 q[++zcnt]=jiaodian(p[i],p[i+1],a,b,c);
    170.             }
    171.         }
    172.     }
    173.     for(int i=1; i<=zcnt; i++)
    174.     {
    175.         p[i]=q[i];
    176.     }
    177.     p[zcnt+1]=q[1];
    178.     p[0]=p[zcnt];
    179.     ccnt=zcnt;
    180. }
    182. int dcmp(double x)
    183. {
    184.     if(fabs(x)<esp) return 0;
    185.     return 1;
    186. }
    188. int solve(double r)
    189. {
    190.     initial();
    191.     for(int i=1; i<=m; i++)
    192.     {
    193.         node ta, tb, tt;//得到平移后的直线
    194.         tt.x = arr[i + 1].y - arr[i].y;
    195.         tt.y = arr[i].x - arr[i + 1].x;
    196.         double k = r / sqrt(tt.x * tt.x + tt.y * tt.y);
    197.         tt.x = tt.x * k;
    198.         tt.y = tt.y * k;
    199.         ta.x = arr[i].x + tt.x;
    200.         ta.y = arr[i].y + tt.y;
    201.         tb.x = arr[i + 1].x + tt.x;
    202.         tb.y = arr[i + 1].y + tt.y;
    203.         double a,b,c;
    204.         GetLine(ta,tb,a,b,c);
    205.         cut(a,b,c);
    206.     }
    207.     double area=0;
    208.     for(int i=1; i<=zcnt; i++)
    209.     {
    210.         area+=p[i].x*p[i+1].y-p[i+1].x*p[i].y;
    211.     }
    212.     area=fabs(area/2.0);
    213.     if(!zcnt&&dcmp(area)==0)
    214.     {
    215.         return 0;
    216.     }
    217.     else
    218.     {
    219.         return 1;
    220.     }
    221. }
    223. void GuiZhengHua()
    224. {
    225.     for(int i=1; i<(m+1)/2; i++)
    226.     {
    227.         swap(arr[i],arr[m-i]);
    228.     }
    229. }
    231. int main()
    232. {
    233.     while(scanf("%d",&m)!=EOF)
    234.     {
    235.         if(m==0) break;
    236.         for(int i=1; i<=m; i++)
    237.         {
    238.             cin>>arr[i].x>>arr[i].y;
    239.         }
    240.         GuiZhengHua();
    241.         arr[m+1]=arr[1];
    242.         double left=0,right=inf,mid;
    243.         while((right-left)>=esp)//二分半径
    244.         {
    245.             mid=(right+left)/2.0;
    246.             if(solve(mid))
    247.             {
    248.                 left=mid;
    249.             }
    250.             else
    251.             {
    252.                 right=mid;
    253.             }
    254.         }
    255.         printf("%.6f\n", left);
    256.     }
    257.     return 0;
    258. }

    6、求圆和矩形相交的面积

    1. struct Point
    2. {
    3.     double x,y;
    4.     Point() {}
    5.     Point(double xx,double yy)
    6.     {
    7.         x=xx;
    8.         y=yy;
    9.     }
    10.     Point operator -(Point s)
    11.     {
    12.         return Point(x-s.x,y-s.y);
    13.     }
    14.     Point operator +(Point s)
    15.     {
    16.         return Point(x+s.x,y+s.y);
    17.     }
    18.     double operator *(Point s)
    19.     {
    20.         return x*s.x+y*s.y;
    21.     }
    22.     double operator ^(Point s)
    23.     {
    24.         return x*s.y-y*s.x;
    25.     }
    26. } p[M];
    27. double len(Point a)
    28. {
    29.     return sqrt(a*a);
    30. }
    31. double dis(Point a,Point b)
    32. {
    33.     return len(b-a);
    34. }
    35. double cross(Point a,Point b,Point c)
    36. {
    37.     return (b-a)^(c-a);
    38. }
    39. double dot(Point a,Point b,Point c)
    40. {
    41.     return (b-a)*(c-a);
    42. }
    43. double area(Point b,Point c,double r)
    44. {
    45.     Point a(0.0,0.0);
    46.     if(dis(b,c)<eps) return 0.0;
    47.     double h=fabs(cross(a,b,c))/dis(b,c);
    48.     if(dis(a,b)>r-eps&&dis(a,c)>r-eps)
    49.     {
    50.         double angle=acos(dot(a,b,c)/dis(a,b)/dis(a,c));
    51.         if(h>r-eps) return 0.5*r*r*angle;
    52.         else if(dot(b,a,c)>0&&dot(c,a,b)>0)
    53.         {
    54.             double angle1=2*acos(h/r);
    55.             return 0.5*r*r*fabs(angle-angle1)+0.5*r*r*sin(angle1);
    56.         }
    57.         else return 0.5*r*r*angle;
    58.     }
    59.     else if(dis(a,b)<r+eps&&dis(a,c)<r+eps) return 0.5*fabs(cross(a,b,c));
    60.     else
    61.     {
    62.         if(dis(a,b)>dis(a,c)) swap(b,c);
    63.         if(fabs(dis(a,b))<eps) return 0.0;
    64.         if(dot(b,a,c)<eps)
    65.         {
    66.             double angle1=acos(h/dis(a,b));
    67.             double angle2=acos(h/r)-angle1;
    68.             double angle3=acos(h/dis(a,c))-acos(h/r);
    69.             return 0.5*dis(a,b)*r*sin(angle2)+0.5*r*r*angle3;
    70.         }
    71.         else
    72.         {
    73.             double angle1=acos(h/dis(a,b));
    74.             double angle2=acos(h/r);
    75.             double angle3=acos(h/dis(a,c))-angle2;
    76.             return 0.5*r*dis(a,b)*sin(angle1+angle2)+0.5*r*r*angle3;
    77.         }
    78.     }
    79. }
    80. int main()
    81. {
    82.     int T,n=4;
    83.     double rx,ry,R;
    84.     scanf("%lf%lf%lf",&rx,&ry,&R);
    85.     scanf("%lf%lf%lf%lf",&p[1].x,&p[1].y,&p[3].x,&p[3].y);
    86.     p[2].x=p[1].x;   p[2].y=p[3].y;   p[4].x=p[3].x;    p[4].y=p[1].y;
    87.     p[5]=p[1];
    88.     Point O(rx,ry);
    89.     for (int i=1; i<=n+1; i++) p[i]=p[i]-O;
    90.     O=Point(0,0);
    91.     double sum=0;
    92.     for (int i=1; i<=n; i++)
    93.     {
    94.         int j=i+1;
    95.         double s=area(p[i],p[j],R);
    96.         if (cross(O,p[i],p[j])>0) sum+=s;
    97.         else sum-=s;
    98.     }
    99.     printf("%.4lf\n",fabs(sum));
    100.     return 0;
    101. }

    7、判断直线是否和圆相交（在圆内部也算）

    1. bool judge(node a,node b)
    2. {
    3.     if( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) -b.r*b.r<=esp)
    4.         return 1;
    5.     return 0;
    6. }
    7. bool Judis(node P1,node P2,node o)
    8. {
    9.     if(judge(P1,o)&&judge(P2,o))
    10.         return true;//如果只判断与圆相交不包含在内部就返回false，因为这是判断两个点都在圆内部
    11.     if(!judge(P1,o)&&judge(P2,o)||judge(P1,o)&&!judge(P2,o))
    12.         return true;
    13.     double A,B,C,dist1,dist2,angle1,angle2;
    14.     if(P1.x==P2.x)
    15.         A=1,B=0,C= -P1.x;
    16.     else if(P1.y==P2.y)
    17.         A=0,B=1,C= -P1.y;
    18.     else
    19.     {
    20.         A = P1.y-P2.y;
    21.         B = P2.x-P1.x;
    22.         C = P1.x*P2.y - P1.y*P2.x;
    23.     }
    24.     dist1 = A *o.x + B * o.y + C;
    25.     dist1 *= dist1;
    26.     dist2 = (A * A + B * B) * o.r * o.r;
    27.     if (dist1 >dist2) return false;
    28.     angle1 = (o.x- P1.x) * (P2.x - P1.x) + (o.y - P1.y) * (P2.y - P1.y);
    29.     angle2 = (o.x - P2.x) * (P1.x - P2.x) + (o.y - P2.y) * (P1.y - P2.y);
    30.     if (angle1 >0 && angle2 > 0) return true;
    31.     return false;
    32. }

    8、圆和正方形相交，相离

    1. //相交：
    2. //a：正方形四个点在圆内（不在圆上）
    3. //b：圆的五点在正方形内（不在正方形边上）（五点是指圆心加上圆的最上下左右四个点，还有正方形四个点都在圆上的情况，这时候要用圆心判断）
    4. //相接触：
    5. //就是上面a,b,中的不在圆上不在正方形边上的条件去掉。
    6. //相离：
    7. //其余就是相离的情况
    8. #include <bits/stdc++.h>
    9. using namespace std;
    10. typedef long long ll;
    11. const double eps=1e-8;
    12. const double PI= acos(-1.0);
    13. const int M = 1e5+7;
    14. struct node
    15. {
    16.     double x,y;
    17. };
    18. node c,t;
    19. double r,s;
    20. double dis(node a,node b)
    21. {
    22.     return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    23. }
    24. int in_cir(node p)//点p是否在圆内2，是否在圆上1，否则0
    25. {
    26.     double d=dis(p,c);
    27.     if(d<r*r)return 2;
    28.     if(d==r*r)return 1;
    29.     return 0;
    30. }
    31. int in_square(node p)//点p是否在正方形内2，是否在正方形边上1，否则0
    32. {
    33.     if(p.x>t.x&&p.x<t.x+s&&p.y>t.y&&p.y<t.y+s)
    34.         return 2;
    35.     else if(p.x==t.x&&p.y>=t.y&&p.y<=t.y+s)
    36.         return 1;
    37.     else if(p.x==t.x+s&&p.y>=t.y&&p.y<=t.y+s)
    38.         return 1;
    39.     else if(p.y==t.y&&p.x>=t.x&&p.x<=t.x+s)
    40.         return 1;
    41.     else if(p.y==t.y+s&&p.x>=t.x&&p.x<=t.x+s)
    42.         return 1;
    43.     else
    44.         return 0;
    45. }
    46. int main()
    47. {
    48.     ios::sync_with_stdio(false);
    49.     cin.tie(0);
    50.     cin>>c.x>>c.y>>r;
    51.     cin>>t.x>>t.y>>s;
    52.     int f=-1;
    53.     if(in_cir(t)==2||in_cir(node{t.x+s,t.y})==2||
    54.        in_cir(node{t.x,t.y+s})==2||in_cir(node{t.x+s,t.y+s})==2)
    55.         f=2;//正方形顶点在圆内
    56.     else if(in_square(node{c.x-r,c.y})==2||in_square(node{c.x+r,c.y})==2
    57.             ||in_square(node{c.x,c.y+r})==2||in_square(node{c.x,c.y-r})==2
    58.             ||in_square(c)==2)
    59.         f=2;//圆的5点在正方形内
    60.     else
    61.     {
    62.         int nm1=0,nm2=0;
    63.         if(in_cir(t)==1)nm1++;
    64.         if(in_cir(node{t.x+s,t.y})==1)nm1++;
    65.         if(in_cir(node{t.x,t.y+s})==1)nm1++;
    66.         if(in_cir(node{t.x+s,t.y+s})==1)nm1++;
    67.         if(in_square(node{c.x-r,c.y})==1) nm2++;
    68.         if(in_square(node{c.x+r,c.y})==1)nm2++;
    69.         if(in_square(node{c.x,c.y+r})==1)nm2++;
    70.         if(in_square(node{c.x,c.y-r})==1)nm2++;
    71.         if(nm1==1||nm2==1)f=1;
    72.         else f=0;
    73.     }
    74.     cout<<f<<endl;
    75.     return 0;
    76. }

    9、运算符重载

    1. const double EPS = 1e-10;
    3. // 浮点数的符号
    4. int sgn(double f)
    5. {
    6.     if(f < -EPS)
    7.         return -1;
    8.     if(f > EPS)
    9.         return 1;
    10.     return 0;
    11. }
    13. // 点、向量
    14. typedef struct pnt // point
    15. {
    16.     double x, y;
    17.     pnt(double _x = 0.0, double _y = 0.0):
    18.     x(_x), y(_y) {}
    20.     // 判相等
    21.     bool operator == (const pnt &rhs) const
    22.     {
    23.         return !sgn(x - rhs.x) && !sgn(y - rhs.y);
    24.     }
    25.     // 两点相减 -> 得出向量
    26.     pnt operator - (const pnt &rhs) const
    27.     {
    28.         return pnt(x - rhs.x, y - rhs.y);
    29.     }
    30.     // 向量点积
    31.     double operator * (const pnt &rhs) const
    32.     {
    33.         return x * rhs.x + y * rhs.y;
    34.     }
    35.     // 向量叉积（的模）
    36.     double operator ^ (const pnt &rhs) const
    37.     {
    38.         return x * rhs.y - rhs.x * y;
    39.     }
    40. } vec; // vector
    42. // VECtor LENgth -> 向量长
    43. double veclen(const vec &v)
    44. {
    45.     return sqrt(v * v);
    46. }
    48. // Point to Segment -> 点 p 到线段 ab 距离
    49. double ps(const pnt &p, const pnt &a, const pnt &b)
    50. {
    51.     if(a == b)
    52.         return veclen(p - a);
    53.     vec ab = b - a, ap = p - a, bp = p - b;
    54.     // 垂足在 a 点左边
    55.     if(sgn(ab * ap) < 0)
    56.         return veclen(ap);
    57.     // 垂足在 b 点右边
    58.     if(sgn(ab * bp) > 0)
    59.         return veclen(bp);
    60.     // 垂足在 ab 上
    61.     return fabs(ab ^ ap) / veclen(ab);
    62. }

    10、单位圆覆盖面积最大技巧

    1. //思路：如果只有一个点，那么输出1 一个覆盖最多点的圆，必然至少有两个点在圆上。枚举两个点，求过这两个点的单位圆，判断有多少个点在圆中，枚举N^2，判断N

    11、叉积

    1. int Area(node a,node b)
    2. {
    3.     Return a.x*b.y-a.y*b.x;
    4. }
    6. //判断两线段的相对位置；
    7. //判断两线段有无交点：
    8. //a,b为一条直线，cd同理,此处重载*
    9. int judge(line a, line b)
    10. {
    11.     if (((a.x2 - a.x1)*(b.y1 - a.y1) - (b.x1 - a.x1)*(a.y2 - a.y1))*((a.x2 - a.x1)*(b.y2 - a.y1) - (b.x2 - a.x1)*(a.y2 - a.y1)) > eps)return 0;
    12.     if (((b.x2 - b.x1)*(a.y1 - b.y1) - (a.x1 - b.x1)*(b.y2 - b.y1))*((b.x2 - b.x1)*(a.y2 - b.y1) - (a.x2 - b.x1)*(b.y2 - b.y1)) > eps)return 0;
    13.     return 1;
    14. }
    15. 或者
    16.     if(((b-a)*(c-a))*((b-a)*(d-a)) > 0 || ((d-c)*(a-c))*((d-c)*(b-c)) > 0)//两条线段根本没有交点 
    17.     {
    18.         puts("0.00");
    19.         continue;
    20.     }
    21. //判断直线与线段有无交点：
    22. //直线ab,线段cd：//重载*为叉积
    23. If(((b-c)*（a-c）)*((b-d)*(a-d)))<=0
    24.     //有交点

    12、已知两条线段四个端点，求交点

    1. point Intersection(point a, point b, point c, point d)
    2. {
    3.     double t = ((d - a)*(c - a))/((b - a)*(d - c));//相似三角形
    4.     return a + (b-a)*fabs(t);
    5. }

    13、map

    1. //用map存点用重载<缩点
    2. point base()const
    3.     {
    4.         if ( x == 0 && y < 0)return point(-x, -y);
    5.         return *this;
    6.     }
    7.     bool operator<(const point&b)const
    8.     {
    9.         point p1 = base();
    10.         point p2 = b.base();
    11.         return p1.x*p2.y < p1.y*p2.x;
    12.     }
    13. //Map中的点只有第一象限的，例如存a=（0，-1），b=（0，1）最终mp[a]=mp[b]=2;

    14、字符串哈希

    1. 求字符串中一定长度的所有不同子串的数量：
    2.     typedef long long ull;//自然哈希，自动取余
    3. const ull has= 233;//去一个较大的质数
    4. const int maxn = 1e6 + 10;
    5. char s[maxn];
    6. vector<ull>ve;
    7. int main()
    8. {
    9.     int n,m;
    10.     scanf("%d%d",&n,&m);
    11.     scanf("%s",s);
    12.     int len=strlen(s);
    13.     ull r=1,sum=0;
    14.     for(int i=0;i<n&&i<len;i++)
    15.     {
    16.         sum=sum*has+s[i];//用数字保存第一个一点长度的字符串
    17.         r*=has;
    18.     }
    19.     if(len>=n)
    20.         ve.push_back(sum);
    21.     for(int i=n;i<len;i++)
    22.     {
    23.         sum=sum*has-s[i-n]*r+s[i];//去掉前一位加上后一位
    24.         ve.push_back(sum);
    25.     }
    26.     sort(ve.begin(),ve.end());//必须排序
    27.     int tot = unique(ve.begin(), ve.end()) - ve.begin();
    28.     cout<<tot<<endl;
    29.     return 0;
    30. }

    15、统计一个字符串最长子序列，经过排序后可以构成回文串：（将字母转化为二进制数字求异或前缀和，若出现多次相同数字，则证明该点与前次出现的点能组成回文串。一个数异或另一个数两次得到原来的数）

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. typedef long long ll;
    4. const int N= 300005;
    5. const int INF=0x3f3f3f3f;
    6. const int mod=1000000007;
    7. typedef pair<int,int>P;
    8. char s[N];
    9. int n;
    10. map<int,int>mp;
    11. int main()
    12. {
    13.     scanf("%d",&n);
    14.     scanf("%s",s+1);
    15.     int now=0,ans=0;
    16.     mp[0]=0;
    17.     for(int i=1;i<=n;i++)
    18.     {
    19.         now^=(1<<(s[i]-'a'));//now与2的几次方异或
    20.         if(mp.count(now)) ans=max(i-mp[now],ans);//异或得到原来的数，说明这一段数出现的次数都是偶数。
    21.         else mp[now]=i;//记录这个值得下标
    22.         for(int j=0;j<=20;j++)
    23.         {
    24.             int y=1<<j;
    25.             if(mp.count(now^y))ans=max(i-mp[now^y],ans);//出现aba这种情况，与b异或后可以得到now，
    26.         }
    27.     }
    28.     printf("%\n",ans);
    29.     return 0;
    30. }