[关闭]
@y20070316 2017-03-01T08:40:45.000000Z 字数 23684 阅读 1020

计算几何

OI

一、半平面交

bzoj2618√
bzoj3190√
bzoj2732
bzoj1038
bzoj1007√
bzoj1137√
bzoj3800

【bzoj3190】【jloi2013】赛车 数形结合+半平面交

分析

按照【bzoj1007】那种用斜率求小于180°的半平面交的方法。
然后把交点的x小于0的部分全都除掉。
注意特判两条线重合的情况。

规则：
①如果露出一个点，那么也要算。
②如果重合，那么也要算。

对此，我们对斜率排序后，保留重合且截距最大的，还有斜率不同的。
判断删除某个半平面的时候，用而不是，确定出。
确定的时候，还要避免重合的情况，往后移，然后再往左移。

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <algorithm>
  5. using namespace std;
  7. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  9. #define LD long double
  11. const int N=16384;
  13. int n;
  14. struct Line {
  15.     int id; LD k,b;
  16.     Line(int _id=0,LD _k=0,LD _b=0):id(_id),k(_k),b(_b){}
  17.     friend int operator < (Line a,Line b) {
  18.         if (a.k!=b.k) return a.k<b.k; else return a.b>b.b;
  19.     }
  20. }p[N];
  21. int ID(Line a,Line b) {
  22.     return a.id<b.id;
  23. }
  25. Line s[N];
  26. int l,r;
  28. int rd(void) {
  29.     int x=0,f=1; char c=getchar();
  30.     for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
  31.     for (;isdigit(c);c=getchar()) x=x*10+c-'0';
  32.     return x*f;
  33. }
  35. LD inter(Line a,Line b) {
  36.     return -(a.b-b.b)/(a.k-b.k);
  37. }
  39. int main(void) {
  40.     #ifndef ONLINE_JUDGE
  41.         freopen("sdchr.in","r",stdin);
  42.         freopen("sdchr.out","w",stdout);
  43.     #endif
  45.     n=rd(); F(i,1,n) p[i].id=i; F(i,1,n) p[i].b=rd(); F(i,1,n) p[i].k=rd();
  47.     sort(p+1,p+n+1);
  48.     int t=0;
  49.     F(i,1,n) {
  50.         Line tmp=p[i];
  51.         int j=i;
  52.         while (j+1<=n&&p[j+1].k==p[i].k)
  53.             j++;
  54.         F(k,i,j)
  55.             if (p[k].b==tmp.b)
  56.                 p[++t]=p[k];
  57.         i=j;
  58.     }
  59.     n=t;
  60.     F(i,1,n) {
  61.         while (r>=2) {
  62.             LD x1=inter(p[i],s[r-1]);
  63.             LD x2=inter(p[i],s[r]);
  64.             if (x1>x2)
  65.                 s[r--]=Line();
  66.             else break;
  67.         }
  68.         s[++r]=p[i];
  69.     }
  70.     t=l=1;
  71.     while (t+1<=r)
  72.         if ((s[t].b==s[t+1].b&&s[t].k==s[t+1].k)||inter(s[t],s[t+1])<0)
  73.             t++;
  74.         else break;
  75.     while (t-1>=l)
  76.         if (s[t].b==s[t-1].b&&s[t].k==s[t-1].k)
  77.             t--;
  78.         else break;
  79.     l=t;
  81.     printf("%d\n",r-l+1);
  82.     sort(s+l,s+r+1,ID);
  83.     F(i,l,r-1)
  84.         printf("%d ",s[i].id);
  85.     printf("%d\n",s[r].id);
  87.     return 0;
  88. }

【bzoj2618】【cqoi2618】凸多边形 模板题

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <algorithm>
  5. using namespace std;
  7. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  9. #define Vector point
  11. const int M=64;
  12. const int L=512;
  14. int m;
  15. struct point {
  16.     double x,y;
  17.     point(double _x=0,double _y=0):x(_x),y(_y){}
  18.     friend point operator + (point a,point b) {
  19.         return point(a.x+b.x,a.y+b.y);
  20.     }
  21.     friend point operator - (point a,point b) {
  22.         return point(a.x-b.x,a.y-b.y);
  23.     }
  24.     point operator * (double w) {
  25.         return point(x*w,y*w);
  26.     }
  27.     friend double operator ^ (point a,point b) {
  28.         return a.x*b.y-a.y*b.x;
  29.     }
  30. }p[M];
  32. int n,tot;
  33. struct Line {
  34.     point x;
  35.     Vector v;
  36.     double ang;
  37.     Line(point _x=point(),Vector _v=point()):x(_x),v(_v){}
  38.     friend int operator < (Line a,Line b) {
  39.         if (a.ang!=b.ang)
  40.             return a.ang<b.ang;
  41.         else return (a.v^(b.x-a.x))<0;
  42.     }
  43.     void Ang(void) {
  44.         ang=atan2(v.y,v.x);
  45.     }
  46. }line[L];
  48. Line s[L];
  49. int l,r;
  51. point it[L];
  52. int len;
  53. double ans;
  55. int rd(void) {
  56.     int x=0,f=1; char c=getchar();
  57.     for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
  58.     for (;isdigit(c);c=getchar()) x=x*10+c-'0';
  59.     return x*f;
  60. }
  62. point Inter(Line a,Line b) {
  63.     Vector u=a.x-b.x;
  64.     double t=(u^b.v)/(b.v^a.v);
  65.     return a.x+a.v*t;
  66. }
  67. int on_right(Line a,point p) {
  68.     return (a.v^(p-a.x))<=0;
  69. }
  70. void HPI(void) {
  71.     sort(line+1,line+tot+1);
  73.     int t=0;
  74.     F(i,1,tot)
  75.         if (line[i].ang!=line[i-1].ang)
  76.             line[++t]=line[i];
  77.     tot=t;
  79.     l=1,r=0;
  80.     F(i,1,tot) {
  81.         while (l<r&&on_right(line[i],Inter(s[r-1],s[r])))
  82.             s[r--]=Line();
  83.         while (l<r&&on_right(line[i],Inter(s[l],s[l+1])))
  84.             s[l++]=Line();
  85.         s[++r]=line[i];
  86.     }
  87.     while (l<r&&on_right(s[l],Inter(s[r-1],s[r])))
  88.         s[r--]=Line();
  89.     s[r+1]=s[l];
  90. }
  92. int main(void) {
  93.     #ifndef ONLINE_JUDGE
  94.         freopen("sdchr.in","r",stdin);
  95.     #endif
  97.     n=rd();
  98.     F(j,1,n) {
  99.         m=rd();
  100.         F(i,1,m) {
  101.             double x=rd(),y=rd();
  102.             p[i]=point(x,y);
  103.         }
  104.         p[m+1]=p[1];
  105.         F(i,1,m)
  106.             line[++tot]=Line(p[i],p[i+1]-p[i]);
  107.     }
  108.     F(i,1,tot) line[i].Ang();
  110.     HPI();
  112.     F(i,l,r)
  113.         it[++len]=Inter(s[i],s[i+1]);
  114.     F(i,2,len-1)
  115.         ans+=fabs(((it[i]-it[1])^(it[i+1]-it[1])))/2.0;
  116.     printf("%0.3lf\n",ans);
  118.     return 0;
  119. }

【bzoj1007】【hnoi2008】水平相交直线 半平面交

题意

给定若干条直线。
求从无限高的地方看下来，能看见哪些直线。

分析

需要明确这样几个概念：
半平面：一条直线的一侧的所有区域。通过一条有向的直线来刻画，该线段的上方就是半平面，半平面的斜率就是有向线段的斜率。
半平面交：若干个半平面的交集，就是半平面交。

先说明一下这道题与半平面交的关系。
想象一下，从无线高的地方看下来，你会看到一个下凸壳。
这道题相当于求所有朝向为轴正方向的直线的半平面交。

我们考虑按照直线的斜率进行从小到大的排序，逐个添加，维护半平面交。

如上图所示，其中为蓝线与黑线的交点，为蓝线与棕线的交点。
假设当前我们添加了黑线、棕线，现在要添加蓝线。蓝线有三种可能，分别对应图中的三条蓝线。由此可得：当时，我们直接添加蓝线，否则将棕线进行删除。

代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  4. #define D(i,a,b) for (int i=(a);i>=(b);i--)
  5. #define fore(v,u) for (vector<int>::iterator v=g[u].begin();v!=g[u].end();v++)
  6. #define LL long long
  7. #define LD long double
  8. LL rd(void) {
  9.     LL x=0,f=1; char c=getchar();
  10.     for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
  11.     for (;isdigit(c);c=getchar()) x=x*10+c-'0';
  12.     return x*f;
  13. }
  14. char rdc(void) {
  15.     char c=getchar();
  16.     while (!isalpha(c))
  17.         c=getchar();
  18.     return c;
  19. }
  21. const int N=65536;
  22. int n;
  23. struct Line {
  24.     int id; double k,b;
  25.     Line(int _id=0,double _k=0,double _b=0):id(_id),k(_k),b(_b){}
  26.     friend int operator < (Line a,Line b) {
  27.         if (a.k!=b.k) return a.k<b.k; else return a.b>b.b;
  28.     }
  29. }line[N];
  30. void Init(void) {
  31.     n=rd();
  32.     F(i,1,n) {
  33.         double k=rd(),b=rd();
  34.         line[i]=Line(i,k,b);
  35.     }
  36. }
  38. Line s[N]; int tot;
  39. double Cross(Line a,Line b) {
  40.     //保证a.k!=b.k，返回交点的x坐标 
  41.     return (a.b-b.b)/(a.k-b.k);
  42. }
  43. int cmp_id(Line a,Line b) {
  44.     return a.id<b.id;
  45. }
  46. void Solve(void) {
  47.     sort(line+1,line+n+1);
  48.     F(i,1,n) {
  49.         if (i!=1&&line[i].k==line[i-1].k)
  50.             continue;
  51.         while (tot>=2) {
  52.             double s1=Cross(s[tot],line[i]);
  53.             double s2=Cross(s[tot-1],line[i]);
  54.             if (s1>=s2)
  55.                 s[tot--]=Line();
  56.             else break;
  57.         }
  58.         s[++tot]=line[i];
  59.     }
  60.     sort(s+1,s+tot+1,cmp_id); F(i,1,tot) printf("%d ",s[i].id); printf("\n");
  61. }
  63. int main(void) {
  64.     #ifndef ONLINE_JUDGE
  65.         freopen("sdchr.in","r",stdin);
  66.     #endif
  67.     Init();
  68.     Solve();
  69.     return 0;
  70. }

二、凸包 & 旋转卡壳

bzoj3533√
bzoj1027√
bzoj2961√
bzoj2300√
bzoj1185√
zoj1081√
hdu2108√
bzoj3203√
bzoj1069√

【bzoj3533】【sdoi2014】向量集 线段树+凸包+三分

题意

维护一个向量集合，在线支持以下操作：
"，"：加入向量，;
"，，，其中为已经加入的向量个数)
询问第个到第个加入的向量与向量，的点积的最大值。 集合初始时为空。

分析

  首先有这样一个结论：点积最大的向量一定在凸包上。
  直观的理解：点积，对于相同的，则要求在上的投影尽可能地大。即要求在的方向上走得越远越好，所以必须要在边界上。
  证明：对于点，点积为


所以

对于这条式子的几何解释为：过点的斜率为的直线，其截距为
所以问题相当于对每个点做一条斜率为的直线，当时，使得解决尽可能的大，当时，使得尽可能的小。
我们考虑对向量所在的直线做一条垂直的线段，并从无穷远的地方开始扫描，则扫描到的最后一个节点就是我们所求。所以一定在凸包上。
总之，对于，点一定在上凸壳上，对于，点一定在下凸壳上。

  确定在凸包上了，我们又有了新发现：凸包上的点按照极角序排序，与的点积是单峰的。所以我们假如能求得凸包，那么在凸包上三分即可解决问题。

  至于区间的凸包怎么求。假如能将区间划分成多个子区间，对于每个子区间求凸包进行三分，再取最大值，那么最终求出来的答案亦满足要求。所以考虑使用线段树，每个区间存区间的所有点的凸包。
  确定使用线段树的结构后，考虑怎样构建凸包。最简单的想法是维护一个set，动态维护凸包。但是太麻烦了，由于我们每次在序列末插入一个点，所以考虑如果对于某个区间，插入的是这个区间的最后一个点，再把整个区间的点建立凸包。

  我写的是zkw线段树，稍微会快一些，然后也是因为中大的那些评委们也会卡常的。

代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  4. #define D(i,a,b) for (int i=(a);i>=(b);i--)
  5. #define fore(v,u) for (vector<int>::iterator v=g[u].begin();v!=g[u].end();v++)
  6. #define LL long long
  7. #define LD long double
  8. const LL MAX=(LL)1e17;
  9. const LL MIN=(LL)-1e17;
  10. LL rd(void) {
  11.     LL x=0,f=1; char c=getchar();
  12.     for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
  13.     for (;isdigit(c);c=getchar()) x=x*10+c-'0';
  14.     return x*f;
  15. }
  16. char rdc(void) {
  17.     char c=getchar();
  18.     while (!isalpha(c))
  19.         c=getchar();
  20.     return c;
  21. }
  22. int decode(int x,LL ans) {
  23.     return x^(ans&0x7fffffff);
  24. }
  26. struct point {
  27.     int x,y;
  28.     point(int _x=0,int _y=0):x(_x),y(_y){}
  29.     friend LL operator / (point a,point b) {
  30.         return (LL)a.x*b.y-(LL)a.y*b.x;
  31.     }
  32.     friend LL operator * (point a,point b) {
  33.         return (LL)a.x*b.x+(LL)a.y*b.y;
  34.     }
  35.     friend int operator < (point a,point b) {
  36.         if (a.x!=b.x) return a.x<b.x; else return a.y<b.y;
  37.     }
  38.     friend point operator - (point a,point b) {
  39.         return point(a.x-b.x,a.y-b.y);
  40.     }
  41. };
  43. const int N=1048576;
  44. int n;
  45. int m; int r[N];
  46. vector<point> pt[N],up[N],dw[N];
  47. void Push(int x,int xl,int xr) {
  48.     r[x]=xr;
  49.     if (x<(1<<m)) {
  50.         int mid=(xl+xr)>>1;
  51.         Push(x<<1,xl,mid);
  52.         Push(x<<1|1,mid+1,xr);
  53.     }
  54. }
  55. void Prework(void) {
  56.     n=rd();
  57.     for (m=1;(1<<m)<=n+1;m++);
  58.     Push(1,0,(1<<m)-1);
  59. }
  60. void Flow(int x) {
  61.     static point tmp[N]; int n=0; F(i,1,pt[x].size()) tmp[++n]=pt[x][i-1];
  62.     sort(tmp+1,tmp+n+1);
  64.     static point t2[N]; int tot=0;
  65.     F(i,1,n) {
  66.         while (tot>=2&&(t2[tot]-t2[tot-1])/(tmp[i]-t2[tot-1])<=0)
  67.             t2[tot--]=point();
  68.         t2[++tot]=tmp[i];
  69.     }
  70.     dw[x].resize(tot+1); F(i,1,tot) dw[x][i]=t2[i];
  72.     tot=0;
  73.     D(i,n,1) {
  74.         while (tot>=2&&(t2[tot]-t2[tot-1])/(tmp[i]-t2[tot-1])<=0)
  75.             t2[tot--]=point();
  76.         t2[++tot]=tmp[i];
  77.     }
  78.     up[x].resize(tot+1); F(i,1,tot) up[x][i]=t2[i];
  79. }
  80. void Insert(int x,point p) {
  81.     for (int now=x+(1<<m);now>0;now>>=1) {
  82.         pt[now].push_back(p);
  83.         if (r[now]==x)
  84.             Flow(now);
  85.     }
  86. }
  87. LL Query(vector<point> &vec,int l,int r,point p) {
  88.     while (r-l>=3) {
  89.         int _l=(l+l+r)/3;
  90.         int _r=(l+r+r)/3;
  91.         if (p*vec[_l]>p*vec[_r])
  92.             r=_r;
  93.         else l=_l;
  94.     }
  95.     LL ans=MIN;
  96.     F(i,l,r)
  97.         ans=max(ans,p*vec[i]);
  98.     return ans;
  99. }
  100. LL Ask(int l,int r,point p) {
  101.     LL ans=MIN;
  102.     for (l--,r++,l+=(1<<m),r+=(1<<m);l^r^1;l>>=1,r>>=1) {
  103.         if (!(l&1)) {
  104.             if (p.y>=0) ans=max(ans,Query(up[l^1],1,up[l^1].size()-1,p));
  105.             if (p.y<=0) ans=max(ans,Query(dw[l^1],1,dw[l^1].size()-1,p));
  106.         }
  107.         if (r&1) {
  108.             if (p.y>=0) ans=max(ans,Query(up[r^1],1,up[r^1].size()-1,p));
  109.             if (p.y<=0) ans=max(ans,Query(dw[r^1],1,dw[r^1].size()-1,p));
  110.         }
  111.     }
  112.     return ans;
  113. }
  115. void Work(void) {
  116.     LL ans=0; char c=rdc(); int tot=0;
  117.     F(cc,1,n) {
  118.         char kd=rdc();
  119.         if (kd=='A') {
  120.             int x=rd(),y=rd();
  121.             if (c!='E')
  122.                 x=decode(x,ans),y=decode(y,ans);
  123.             Insert(++tot,point(x,y));
  124.         }
  125.         else if (kd=='Q') {
  126.             int x=rd(),y=rd(),l=rd(),r=rd();
  127.             if (c!='E')
  128.                 x=decode(x,ans),y=decode(y,ans),l=decode(l,ans),r=decode(r,ans);
  129.             ans=Ask(l,r,point(x,y));
  130.             printf("%lld\n",ans);
  131.         }
  132.     }
  133. }
  135. int main(void) {
  136.     #ifndef ONLINE_JUDGE
  137.         freopen("sdchr.in","r",stdin);
  138.         freopen("sdchr.out","w",stdout);
  139.     #endif
  140.     Prework();
  141.     Work();
  142.     return 0;
  143. }

【bzoj1027】合金 数形结合+Floyd求最小环

分析

数形结合+计算几何+Floyd最小环。
http://blog.csdn.net/popoqqq/article/details/40539273

代码

  1. #include <cstdio>
  2. #include <climits>
  3. #include <cmath>
  4. #include <algorithm>
  5. using namespace std;
  7. #define rep(i,a,b) for (int i=(a);i<=(b);i++)
  9. const int M=512;
  10. const int N=512;
  11. const int MAX=INT_MAX>>1;
  12. const double EPS=1e-15;
  14. int cmp(double x);
  16. int m,n;
  17. struct point
  18. {
  19.     double x,y;
  20.     point(double _x=0,double _y=0) {
  21.         x=_x,y=_y;
  22.     }
  23.     friend point operator - (point a,point b) {
  24.         return point(a.x-b.x,a.y-b.y);
  25.     }
  26.     friend point operator * (point a,point b) {
  27.         return point(a.x*b.x,a.y*b.y);
  28.     }
  29.     friend int operator == (point a,point b) {
  30.         return !cmp(a.x-b.x)&&!cmp(a.y-b.y);
  31.     }
  32.     friend int operator != (point a,point b) {
  33.         return !(a==b);
  34.     }
  35. }mer[M],prd[N];
  37. int f[M][M];
  38. int res;
  40. void Init(void) {
  41.     scanf("%d%d",&m,&n);
  42.     rep(i,1,m) {
  43.         double x,y; scanf("%lf%lf%*lf",&x,&y);
  44.         mer[i]=point(x,y);
  45.     }
  46.     rep(i,1,n) {
  47.         double x,y; scanf("%lf%lf%*lf",&x,&y);
  48.         prd[i]=point(x,y);
  49.     }
  50. }
  52. int cmp(double x)
  53. {
  54.     if(fabs(x)<EPS)  return 0;
  55.     return x>0?1:-1;
  56. }
  58. double det(point a,point b) {
  59.     return a.x*b.y-a.y*b.x;
  60. }
  62. int Left(point k,point a,point b) {
  63.     double t=det(b-a,k-a);
  64.     return t>0;
  65. }
  66. int On(point k,point a,point b) {
  67.     if (cmp(det(k-a,b-a))!=0) return 0;
  68.     if (!(cmp(min(a.x,b.x)-k.x)<=0&&cmp(k.x-max(a.x,b.x))<=0)) return 0;
  69.     if (!(cmp(min(a.y,b.y)-k.y)<=0&&cmp(k.y-max(a.y,b.y))<=0)) return 0;
  70.     return 1;
  71. }
  73. /*
  74. bool On(const point &a,const point &b,const point &c) { 
  75.     return !cmp(det(a-b,c-b))&&cmp((a.x-b.x)*(a.x-c.x))<=0&&cmp((a.y-b.y)*(a.y-c.y))<=0; 
  76. }
  77. */
  79. int Check(point a,point b) {
  80.     rep(i,1,n) {
  81.         int t1=Left(prd[i],a,b);
  82.         int t2=On(prd[i],a,b);
  83.         if (!t1&&!t2) return 0;
  84.     }
  85.     return 1;
  86. }
  88. void MakeGraph(void) {
  89.     rep(i,1,m) rep(j,1,m) f[i][j]=MAX;
  90.     rep(i,1,m) rep(j,1,m)
  91.         if (Check(mer[i],mer[j]))
  92.             f[i][j]=1;
  93. }
  95. int Floyd(void) {
  96.     rep(i,1,m) {
  97.         int mrk=1;
  98.         rep(j,1,n) if (mer[i]!=prd[j]) {
  99.             mrk=0;
  100.             break;
  101.         }
  102.         if (mrk) return 1;
  103.     }
  105.     rep(i,1,m) rep(j,1,m) {
  106.         int mrk=1;
  107.         rep(k,1,n)
  108.             if (!On(prd[k],mer[i],mer[j])) {
  109.                 mrk=0;
  110.                 break;
  111.             }
  112.         if (mrk) return 2;
  113.     }
  115.     /*
  116.     rep(i,1,m) {
  117.         rep(j,1,m)
  118.             if (f[i][j]!=MAX)
  119.                 printf("%d ",f[i][j]);
  120.             else printf("0 ");
  121.         printf("\n");
  122.     }
  123.     */
  125.     int ans=MAX;
  126.     rep(k,1,m) rep(i,1,m) rep(j,1,m)
  127.         f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
  128.     rep(i,1,m) ans=min(ans,f[i][i]);
  129.     return ans!=MAX?ans:-1;
  130. }
  132. int main(void) {
  133.     #ifndef ONLINE_JUDGE
  134.     freopen("bzoj1027.in","r",stdin);
  135.     freopen("bzoj1027.out","w",stdout);
  136.     #endif
  138.     Init();
  139.     MakeGraph();
  141.     res=Floyd();
  142.     printf("%d\n",res);
  144.     return 0;
  145. }

【bzoj2961】共点圆 cdq分治+凸包

题意

      在平面直角坐标系中，Wayne需要你完成次操作，操作只有两种：
：表示在坐标系中加入一个以为圆心且过原点的圆。
：表示询问点是否在所有已加入的圆的内部（含圆周），且至少在一个圆内部（含圆周）。
      为了减少你的工作量，题目保证圆心严格在x轴上方（纵坐标为正），且横坐标非零。
      数据范围：

分析

      我们考虑怎么判定一个点是否在一个以半径为、以为圆心的圆上。
      我们有：

①②③

      将①②代入③，化简得到：

      所以，点在过原点的以为圆心的圆上，当且仅当在半平面内。
      假如要判定一个点是否被所有圆覆盖，那么就看它之前的所有圆心是否都在这个点对应的半平面内。
      现在的问题被转化为：
①向平面内加一个点
②给一个半平面，问是否之前添加的所有点都在半平面内
      由于这个问题满足两个性质：①可以离线 ②可以操作间互不影响，所以我们考虑使用按照时间进行分治的方法。
      问题被简化为：给定平面内的一堆点，多次给定一个半平面，问这个半平面是否覆盖所有的点。
      这是一个很简单的问题。如何刻画一个半平面覆盖所有的点？即所有的点都在半平面的上面。我们把半平面用一个向量进行表示，向量的上边表示半平面内，下边表示半平面外。那么，即要求所有点在该向量的逆时针方向，直接使用叉积进行判断就行了。
      但是点太多了，会TLE。考虑优化。影响答案的点一定在凸包=上凸壳+下凸壳上。且凸壳上的点与当前向量构成的叉积是单峰的（单谷的）。考虑在凸包上二分就好了。当然也可以用三分，还有直接按照半平面进行极角排序，然后two pointer扫一遍。
      其实有一种不用cdq分治的想法。直接使用平衡树动态维护凸包就好了。考虑使用set来实现平衡树，其实也很简便。

代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  4. #define D(i,a,b) for (int i=(a);i>=(b);i--)
  5. #define fore(v,u) for (vector<int>::iterator v=g[u].begin();v!=g[u].end();v++)
  6. #define LL long long
  7. #define LD double
  8. LL rd(void) {
  9.     LL x=0,f=1; char c=getchar();
  10.     for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
  11.     for (;isdigit(c);c=getchar()) x=x*10+c-'0';
  12.     return x*f;
  13. }
  14. char rdc(void) {
  15.     char c=getchar();
  16.     while (!isalpha(c))
  17.         c=getchar();
  18.     return c;
  19. }
  21. #define N 524288
  23. struct point {
  24.     LD x,y;
  25.     point(LD _x=0,LD _y=0):x(_x),y(_y){}
  26.     friend point operator - (point a,point b) {
  27.         return point(a.x-b.x,a.y-b.y);
  28.     }
  29.     friend LD operator / (point a,point b) {
  30.         return a.x*b.y-a.y*b.x;
  31.     }
  32.     friend int operator < (point a,point b) {
  33.         if (a.x!=b.x) return a.x<b.x; else return a.y<b.y;
  34.     }
  35. }org;
  37. int m;
  38. struct OP {
  39.     int kd; point p;
  40.     OP(int _kd=0,point _p=point()):kd(_kd),p(_p){}
  41. }op[N];
  42. int ans[N],cnt[N];
  44. point p[N]; int n;
  45. point s_dw[N]; int tot_dw;
  46. point s_up[N]; int tot_up;
  47. void Graham(void) {
  48.     sort(p+1,p+n+1);
  50.     while (tot_dw>0) s_dw[tot_dw--]=point();
  51.     F(i,1,n) {
  52.         while (tot_dw>=2&&(s_dw[tot_dw]-s_dw[tot_dw-1])/(p[i]-s_dw[tot_dw-1])<=0)
  53.             s_dw[tot_dw--]=point();
  54.         s_dw[++tot_dw]=p[i];
  55.     }
  57.     while (tot_up>0) s_up[tot_up--]=point();
  58.     D(i,n,1) {
  59.         while (tot_up>=2&&(s_up[tot_up]-s_up[tot_up-1])/(p[i]-s_up[tot_up-1])<=0)
  60.             s_up[tot_up--]=point();
  61.         s_up[++tot_up]=p[i];
  62.     }
  63. }
  65. #define x0 now.x
  66. #define y0 now.y
  67. #define A 0.00
  68. #define B 100.00
  69. int Check(point now) {
  70.     if (y0==0)
  71.         return (2*x0*s_dw[1].x>=x0*x0+y0*y0&&2*x0*s_dw[tot_dw].x>=x0*x0+y0*y0);
  72.     point a(A,(x0*x0+y0*y0-2*x0*A)/(2*y0));
  73.     point b(B,(x0*x0+y0*y0-2*x0*B)/(2*y0));
  74.     if (y0>0) {
  75.         int l=1,r=tot_dw;
  76.         while (r-l>=3) {
  77.             int _l=(l+l+r)/3;
  78.             int _r=(l+r+r)/3;
  79.             LD ql=(b-a)/(s_dw[_l]-a); if (ql<0) return 0;
  80.             LD qr=(b-a)/(s_dw[_r]-a); if (qr<0) return 0;
  81.             if (ql<qr) r=_r; else l=_l;
  82.         }
  83.         F(i,l,r) if ((b-a)/(s_dw[i]-a)<0) return 0;
  84.     }
  85.     else if (y0<0) {
  86.         swap(a,b);
  87.         int l=1,r=tot_up;
  88.         while (r-l>=3) {
  89.             int _l=(l+l+r)/3;
  90.             int _r=(l+r+r)/3;
  91.             LD ql=(b-a)/(s_up[_l]-a); if (ql<0) return 0;
  92.             LD qr=(b-a)/(s_up[_r]-a); if (qr<0) return 0;
  93.             if (ql<qr) r=_r; else l=_l;
  94.         }
  95.         F(i,l,r) if ((b-a)/(s_up[i]-a)<0) return 0;
  96.     }
  97.     return 1;
  98. }
  99. void Solve(int l,int r) {
  100.     if (l==r) return;
  101.     int mid=(l+r)>>1;
  102.     if (l<=mid) Solve(l,mid);
  103.     if (mid+1<=r) Solve(mid+1,r);
  104.     while (n>0) p[n--]=point(); F(i,l,mid) if (op[i].kd==0) p[++n]=op[i].p; if (!n) return;
  105.     Graham();
  106.     F(i,mid+1,r) if (op[i].kd==1) {
  107.         if (ans[i]) ans[i]=Check(op[i].p);
  108.         cnt[i]++;
  109.     } 
  110. }
  112. int main(void) {
  113.     #ifndef ONLINE_JUDGE
  114.         freopen("sdchr.in","r",stdin);
  115.     #endif
  117.     m=rd();
  118.     F(i,1,m) {
  119.         int kd=rd(); LD x,y; scanf("%lf%lf",&x,&y);
  120.         op[i]=OP(kd,point(x,y));
  121.     }
  123.     F(i,1,m) ans[i]=1;
  124.     Solve(1,m);
  125.     F(i,1,m) if (op[i].kd==1&&!cnt[i]) ans[i]=0;
  126.     F(i,1,m) if (op[i].kd==1) if (ans[i]) printf("Yes\n"); else printf("No\n");
  128.     return 0;
  129. }

【bzoj2300】【haoi2011】防线修建 离线处理+动态维护凸包

代码

  1. #include <bits/stdc++.h>
  2. #include <algorithm>
  3. using namespace std;
  4. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  5. #define D(i,a,b) for (int i=(a);i>=(b);i--)
  6. #define fore(v,u) for (vector<int>::iterator v=g[u].begin();v!=g[u].end();v++)
  7. #define LL long long
  8. #define LD long double
  9. LL rd(void) {
  10.     LL x=0,f=1; char c=getchar();
  11.     for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
  12.     for (;isdigit(c);c=getchar()) x=x*10+c-'0';
  13.     return x*f;
  14. }
  15. char rdc(void) {
  16.     char c=getchar();
  17.     while (!isalpha(c))
  18.         c=getchar();
  19.     return c;
  20. }
  22. struct point {
  23.     double x,y;
  24.     point(double _x=0,double _y=0):x(_x),y(_y){}
  25.     friend point operator - (point a,point b) {
  26.         return point(a.x-b.x,a.y-b.y);
  27.     }
  28.     friend int operator < (point a,point b) {
  29.         if (a.x!=b.x) return a.x<b.x; else return a.y<b.y;
  30.     }
  31.     friend double operator / (point a,point b) {
  32.         return a.x*b.y-a.y*b.x;
  33.     }
  34.     double norm(void) {
  35.         return sqrt(x*x+y*y);
  36.     }
  37.     void Read(void) {
  38.         x=rd(),y=rd();
  39.     }
  40. };
  42. set<point> s;
  43. double sum;
  44. void Add(point x) {
  45.     set<point>::iterator r=lower_bound(s.begin(),s.end(),x),l=r,t; l--;
  46.     if ((x-*l)/(*r-*l)>0) return;
  47.     sum-=(*r-*l).norm();
  48.     while (1) {
  49.         t=r; r++;
  50.         if (r==s.end()) break;
  51.         if ((*t-x)/(*r-x)<0) break;
  52.         sum-=(*r-*t).norm();
  53.         s.erase(t);
  54.     }
  55.     while (1) {
  56.         if (l==s.begin()) break;
  57.         t=l; l--;
  58.         if ((x-*l)/(*t-*l)>0) break;
  59.         sum-=(*t-*l).norm();
  60.         s.erase(t);
  61.     }
  62.     s.insert(x);
  63.     l=r=s.find(x);
  64.     l--,r++;
  65.     sum+=(*r-x).norm();
  66.     sum+=(x-*l).norm();
  67. }
  69. #define M 262144
  70. int m; point p[M]; int v[M];
  71. int q,op[M][2]; double ans[M];
  73. int main(void) {
  74.     #ifndef ONLINE_JUDGE
  75.         freopen("sdchr.in","r",stdin);
  76.     #endif
  78.     int n=rd(),x=rd(),y=rd();
  79.     s.insert(point(0,0));
  80.     s.insert(point(n,0));
  81.     s.insert(point(x,y));
  82.     sum+=(point(0,0)-point(x,y)).norm();
  83.     sum+=(point(x,y)-point(n,0)).norm();
  85.     m=rd(); F(i,1,m) p[i].Read();
  86.     q=rd(); 
  87.     F(i,1,q) if (rd()==2) op[i][0]=2; else op[i][0]=1,v[op[i][1]=rd()]=1;
  88.     F(i,1,m) if (!v[i]) Add(p[i]);
  89.     D(i,q,1)
  90.         if (op[i][0]==2) ans[i]=sum; else Add(p[op[i][1]]);
  91.     F(i,1,q) if (op[i][0]==2) printf("%0.2lf\n",ans[i]);
  93.     return 0;
  94. }

【bzoj1185】【hnoi2007】最小矩形覆盖 凸包+旋转卡壳

代码

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. using namespace std;
  5. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  7. #define INF 1e30
  8. #define EPS 1e-8
  10. #define N 65536
  12. int n;
  13. struct point {
  14.     double x,y;
  15.     point(double _x=0,double _y=0) {
  16.         x=_x,y=_y;
  17.     }
  18.     friend point operator + (point a,point b) {
  19.         return point(a.x+b.x,a.y+b.y);
  20.     }
  21.     friend point operator - (point a,point b) {
  22.         return point(a.x-b.x,a.y-b.y);
  23.     }
  24.     point operator * (double val) {
  25.         return point(x*val,y*val);
  26.     }
  27.     void Read(void) {
  28.         scanf("%lf%lf",&x,&y);
  29.     }
  30.     double norm(void) {
  31.         return sqrt(pow(x,2)+pow(y,2));
  32.     }
  33. }p[N],org;
  34. double dot(point a,point b) {
  35.     return a.x*b.x+a.y*b.y;
  36. }
  37. double det(point a,point b) {
  38.     return a.x*b.y-a.y*b.x;
  39. }
  40. int cmp(point a,point b) {
  41.     return det(a-org,b-org)>0;
  42. }
  44. int tot;
  45. point s[N];
  47. double ans;
  48. point t[4];
  50. void Graham(void) {
  51.     F(i,2,n) if (p[i].y<p[1].y||p[i].y==p[1].y&&p[i].x<p[1].x) swap(p[1],p[i]);
  52.     org=p[1]; sort(p+2,p+n+1,cmp);
  53.     F(i,1,n) {
  54.         while (tot>=2&&det(s[tot]-s[tot-1],p[i]-s[tot-1])<=0)
  55.             s[tot--]=point();
  56.         s[++tot]=p[i];
  57.     }
  58.     s[0]=s[tot];
  59. }
  61. void Rot(void) {
  62.     int l=0,r=0,p=0; ans=INF;
  63.     F(i,1,tot-1) {
  64.         if (det(s[1]-s[0],s[i]-s[0])>det(s[1]-s[0],s[p]-s[0])-EPS) p=i;
  65.         if (dot(s[1]-s[0],s[i]-s[0])>dot(s[1]-s[0],s[r]-s[0])-EPS) r=i;
  66.         if (dot(s[1]-s[0],s[i]-s[0])<dot(s[1]-s[0],s[l]-s[0])+EPS) l=i;
  67.     }
  68.     F(i,0,tot-1) {
  69.         double D=(s[i+1]-s[i]).norm();
  70.         while (det(s[i+1]-s[i],s[p+1]-s[i])>det(s[i+1]-s[i],s[p]-s[i])-EPS)
  71.             p=(p+1)%tot;
  72.         while (dot(s[i+1]-s[i],s[r+1]-s[i])>dot(s[i+1]-s[i],s[r]-s[i])-EPS)
  73.             r=(r+1)%tot;
  74.         while (dot(s[i+1]-s[i],s[l+1]-s[i])<dot(s[i+1]-s[i],s[l]-s[i])+EPS)
  75.             l=(l+1)%tot;
  76.         double L=dot(s[i+1]-s[i],s[l]-s[i])/D;
  77.         double R=dot(s[i+1]-s[i],s[r]-s[i])/D;
  78.         double H=det(s[i+1]-s[i],s[p]-s[i])/D; H=fabs(H);
  79.         double tmp=(R-L)*H;
  80.         if (tmp<ans) {
  81.             ans=tmp;
  82.             t[0]=s[i]+(s[i+1]-s[i])*(R/D);
  83.             t[1]=t[0]+(s[r]-t[0])*(H/(t[0]-s[r]).norm());
  84.             t[2]=t[1]-(t[0]-s[i])*((R-L)/(s[i]-t[0]).norm());
  85.             t[3]=t[2]-(t[1]-t[0]);
  86.         }
  87.     }
  88. }
  90. int main(void) {
  91.     #ifndef ONLINE_JUDGE
  92.         freopen("a.in","r",stdin);
  93.     #endif
  95.     scanf("%d",&n); F(i,1,n) p[i].Read();
  97.     Graham();
  99.     Rot();
  100.     printf("%0.5lf\n",ans);
  101.     int x=0; F(i,1,3) if (t[i].y<t[x].y||t[i].y==t[x].y&&t[i].x<t[x].x) x=i;
  102.     F(i,0,3) printf("%0.5lf %0.5lf\n",t[(i+x)%4].x,t[(i+x)%4].y);
  104.     return 0;
  105. }

【zoj1081】Points Within - 判断一个点是否在多边形内

题意

给定一个任意的多边形，判断点在不在多边形内。

分析

过当前点做一条射线。
看经过的节点的情况。
为了特判经过端点的情况，把所有线段的值较大的端点当成空心的点。

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <algorithm>
  4. using namespace std;
  5. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  6. #define INF 0x7fffffff
  7. int rd(void) {
  8.     int x=0,f=1; char c=getchar();
  9.     for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
  10.     for (;isdigit(c);c=getchar()) x=x*10+c-'0';
  11.     return x*f;
  12. }
  14. #define N 128
  15. int n,m;
  16. struct point {
  17.     double x,y;
  18.     point(double _x=0,double _y=0) {
  19.         x=_x,y=_y;
  20.     }
  21.     friend point operator - (point a,point b) {
  22.         return point(a.x-b.x,a.y-b.y);
  23.     }
  24.     void Read(void) {
  25.         scanf("%lf%lf",&x,&y);
  26.     }
  27. }p[N];
  28. double det(point a,point b) {
  29.     return a.x*b.y-a.y*b.x;
  30. }
  32. int Online(point a,point b,point x) {
  33.     if (det(x-a,b-a)!=0) return 0;
  34.     double minx=min(a.x,b.x),maxx=max(a.x,b.x);
  35.     double miny=min(a.y,b.y),maxy=max(a.y,b.y);
  36.     return minx<=x.x&&x.x<=maxx&&miny<=x.y&&x.y<=maxy;
  37. }
  38. int PNPoly(point x) {
  39.     int c=0;
  40.     F(i,0,n-1)
  41.         if (Online(p[i],p[i+1],x))
  42.             return 1;
  43.     F(i,0,n-1) {
  44.         double k=det(p[i+1]-p[i],x-p[i]);
  45.         if (k>0&&p[i].y<=x.y&&x.y<p[i+1].y) c++;
  46.         if (k<0&&p[i+1].y<=x.y&&x.y<p[i].y) c--;
  47.     }
  48.     return c!=0;
  49. }
  51. int main(void) {
  52.     #ifndef ONLINE_JUDGE
  53.         freopen("a.in","r",stdin);  
  54.     #endif
  56.     F(c,1,INF) {
  57.         n=rd(); if (!n) break; m=rd();
  58.         F(i,1,n) p[i].Read(); p[0]=p[n];
  60.         if (n>=2) {
  61.             double t=det(p[2]-p[1],p[1]-p[0]);
  62.             if (t>0) F(i,0,n>>1) swap(p[i],p[n-i]);
  63.         }
  65.         if (c!=1) printf("\n");
  66.         printf("Problem %d:\n",c);
  67.         F(i,1,m) {
  68.             point x; x.Read();
  69.             if (PNPoly(x)) printf("Within\n"); else printf("Outside\n");
  70.         }
  71.     }
  72.     return 0;
  73. }

【hdu2108】Shape of HDU - 判定是不是凸包

题意

如标题所示

分析

使用判断。
记得判断第一个点与最后一个点的连边也要满足是凸的。

在直观理解叉积上，需要注意两点。
一个是平移的观点。
另一个是>0在下面，<0在上面，=0共线。

如果凸包可能是顺时针的，可能是逆时针的。
需要这样进行调整：

  1. double t=det(p[2]-p[1],p[1]-p[0]);
  2. if (t>0) F(i,0,n>>1) swap(p[i],p[n-i]);

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <algorithm>
  4. using namespace std;
  5. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  6. int rd(void) {
  7.     int x=0,f=1; char c=getchar();
  8.     for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
  9.     for (;isdigit(c);c=getchar()) x=x*10+c-'0';
  10.     return x*f;
  11. }
  13. #define N 128
  14. int n;
  15. struct point {
  16.     double x,y;
  17.     point(double _x=0,double _y=0) {
  18.         x=_x,y=_y;
  19.     }
  20.     friend point operator - (point a,point b) {
  21.         return point(a.x-b.x,a.y-b.y);
  22.     }
  23.     void Read(void) {
  24.         x=rd(),y=rd();
  25.     }
  26. }p[N];
  27. double det(point a,point b) {
  28.     return a.x*b.y-a.y*b.x;
  29. }
  31. int is_convex(point *p,int n) {
  32.     F(i,2,n) {
  33.         double t=det(p[i]-p[i-1],p[i-1]-p[i-2]);
  34.         if (t>0) return 0;
  35.     }
  36.     return 1;
  37. }
  39. int main(void) {
  40.     #ifndef ONLINE_JUDGE
  41.         freopen("a.in","r",stdin);
  42.     #endif
  44.     while (1) {
  45.         n=rd();
  46.         if (!n) break;
  47.         if (n<=2) {
  48.             printf("concave\n");
  49.             continue;
  50.         }
  51.         F(i,1,n) p[i].Read(); p[0]=p[n];
  53.         /*
  54.         double t=det(p[2]-p[1],p[1]-p[0]);
  55.         if (t>0) F(i,0,n>>1) swap(p[i],p[n-i]);
  56.         */
  58.         if (is_convex(p,n)) printf("convex\n"); else printf("concave\n");
  59.     }
  60.     return 0;
  61. }

【bzoj1069】【scoi2007】最大土地面积 凸包+旋转卡壳

题意

      在某块平面土地上有个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成的多边形面积最大。

分析

      首先，我们选择的四个点一定是多边形的顶点。所以我们先用Graham算法求出凸包。注意求凸包的正确姿势。det(a,b)<0，直接说明a在b的上面，类似的，有det(a,b)=0和det(a,b)>0。

      然后，考虑怎么求最大的面积。我们可以考虑枚举一条对角线，暴力算左边和右边的最优情况。时间复杂度为，但是会TLE。

      考虑根据凸包的性质进行优化。我们枚举对角线上的一个点，按照极角序枚举另一个点，那么最大的面积的点必然在单调的移动。所以优化到了。这貌似叫旋转卡壳？

      关于实现上，多边形的面积考虑使用叉积来求。

代码

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. using namespace std;
  5. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  6. #define MIN -1e30
  8. #define N 2048
  10. int n;
  11. struct point {
  12.     double x,y;
  13.     point(double _x=0,double _y=0) {
  14.         x=_x,y=_y;
  15.     }
  16.     friend point operator - (point a,point b) {
  17.         return point(a.x-b.x,a.y-b.y);
  18.     }
  19.     void Read(void) {
  20.         scanf("%lf%lf",&x,&y);
  21.     }
  22. }p[N],org;
  23. double det(point a,point b) {
  24.     return a.x*b.y-a.y*b.x;
  25. }
  26. int cmp(point a,point b) {
  27.     return det(a-org,b-org)<0;
  28. }
  29. double sqr(point a,point b,point c) {
  30.     return fabs(det(b-a,c-a))/2;
  31. }
  33. point s[N]; int tot;
  34. void Graham(void) {
  35.     int k=1; F(i,2,n) if (p[i].y<p[k].y||p[i].y==p[k].y&&p[i].x<p[k].x) k=i;
  36.     swap(p[1],p[k]); org=p[1];
  37.     sort(p+2,p+n+1,cmp);
  38.     s[++tot]=p[1],s[++tot]=p[2];
  39.     F(i,3,n) {
  40.         while (tot>=2&&det(s[tot]-s[tot-1],p[i]-s[tot-1])>=0)
  41.             s[tot--]=point();
  42.         s[++tot]=p[i];
  43.     }
  44. }
  45. double RC(void) {
  46.     double ans=MIN;
  47.     F(x,1,tot) {
  48.         int a=x%tot+1;
  49.         int b=(x+2)%tot+1;
  50.         F(y,x+2,tot) {
  51.             while (a%tot+1!=y&&sqr(s[x],s[y],s[a])<sqr(s[x],s[y],s[a%tot+1]))
  52.                 a=a%tot+1;
  53.             while (b%tot+1!=x&&sqr(s[x],s[y],s[b])<sqr(s[x],s[y],s[b%tot+1]))
  54.                 b=b%tot+1;
  55.             ans=max(ans,sqr(s[x],s[y],s[a])+sqr(s[x],s[y],s[b]));
  56.         }
  57.     }
  58.     return ans;
  59. }
  61. int main(void) {
  62.     #ifndef ONLINE_JUDGE
  63.         freopen("a.in","r",stdin);
  64.     #endif
  66.     scanf("%d",&n); F(i,1,n) p[i].Read();
  68.     Graham();
  69.     double ans=RC();
  70.     printf("%.3lf\n",ans);
  71.     return 0;
  72. }

【bzoj3203】【sdoi2013】保护出题人 凸包+三分

分析

PoPoQQQ题解 之 传送门

关键掌握一下三分的写法。

  1. double Query(point o) {
  2.     int l=1,r=tot;
  3.     while (r-l>=3) {
  4.         int l_mid=(l+l+r)/3,r_mid=(l+r+r)/3;
  5.         double _l=slope(s[l_mid],o);
  6.         double _r=slope(s[r_mid],o);
  7.         if (_l>_r)
  8.             r=r_mid;
  9.         else l=l_mid;
  10.     }
  11.     double res=0;
  12.     F(i,l,r)
  13.         res=max(res,slope(s[i],o));
  14.     return res;
  15. }

大范围三分，小范围枚举，这样肯定是没有问题的。

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <algorithm>
  4. using namespace std;
  5. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  6. #define LL long long
  7. #define INF 1e30
  8. LL rd(void) {
  9.     LL x=0,f=1; char c=getchar();
  10.     for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
  11.     for (;isdigit(c);c=getchar()) x=x*10+c-'0';
  12.     return x*f;
  13. }
  15. #define N 131072
  17. int n; LL d;
  18. LL a[N],x[N];
  20. int tot;
  21. struct point {
  22.     double x,y;
  23.     point(double _x=0,double _y=0) {
  24.         x=_x,y=_y;
  25.     }
  26.     friend point operator - (point a,point b) {
  27.         return point(a.x-b.x,a.y-b.y);
  28.     }
  29.     friend double operator ^ (point a,point b) {
  30.         return a.x*b.y-a.y*b.x;
  31.     }
  32. }s[N];
  33. void Add(point a) {
  34.     while (tot>=2)
  35.         if (((s[tot]-s[tot-1])^(a-s[tot-1]))<=0)
  36.             s[tot--]=point();
  37.         else break;
  38.     s[++tot]=a;
  39. }
  40. double slope(point a,point b) {
  41.     return (a.y-b.y)/(a.x-b.x);
  42. }
  43. double Query(point o) {
  44.     int l=1,r=tot;
  45.     while (r-l>=3) {
  46.         int l_mid=(l+l+r)/3,r_mid=(l+r+r)/3;
  47.         double _l=slope(s[l_mid],o);
  48.         double _r=slope(s[r_mid],o);
  49.         if (_l>_r)
  50.             r=r_mid;
  51.         else l=l_mid;
  52.     }
  53.     double res=0;
  54.     F(i,l,r)
  55.         res=max(res,slope(s[i],o));
  56.     return res;
  57. }
  59. int main(void) {
  60.     #ifndef ONLINE_JUDGE
  61.         freopen("a.in","r",stdin);
  62.     #endif
  64.     n=rd(),d=rd();
  65.     F(i,1,n) a[i]=rd(),x[i]=rd();
  66.     F(i,1,n) a[i]+=a[i-1];
  68.     double sum=0;
  69.     F(i,1,n) {
  70.         Add(point(i*d,a[i-1]));
  71.         double t=Query(point(i*d+x[i],a[i]));
  72.         sum+=t;
  73.     }
  74.     printf("%.0lf\n",sum);
  76.     return 0;
  77. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注