P2521 [HAOI2011]防线修建

题目链接：P2521 [HAOI2011]防线修建

题意：给定点集

每次有两种操作：

1. 删除一个点（除开(0, 0), (n, 0), 与指定首都(x, y)）

2. 询问上凸包长度

至于为什么是上凸包 “三角形任意两边之和大于第三边”就可以证

我们的套路不包括只做删除的在线凸包问题所以把询问逆序操作

根据套路只有插入操作的对答案贡献不独立的凸包问题我们使用平衡树维护

其实只用求前驱后继所以蒟蒻就偷懒用了STL的set

一开始构造最后删完的点集的凸包

每次插入一个点时

如果它在当前凸包内部或凸包上那么不影响答案直接忽略

如果在外部从近到远询问它前面的点类似于Andrew一开始插入点的做法

再从近到远询问它后面的点做法同样

记得维护答案

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <set>
  6 using namespace std;
  7 const int N = 1e5 + 5;
  8 const int Q = 2e5 + 5;
  9 const double eps = 1e-8;
 10 struct Node{
 11     int id;
 12     double x, y;
 13 }node[N], stk[N], nl;
 14 set<Node> st;
 15 int rf[N];
 16 struct Query{
 17     int x, y;
 18 }q[Q];
 19 double anss[N];
 20 int as;
 21 int n, m, cx, cy, qs;
 22 int top;
 23 double ans;
 24 bool ask[N];
 25 
 26 Node operator - (const Node& x, const Node& y){
 27     return (Node){0, x.x - y.x, x.y - y.y}; 
 28 }
 29 
 30 bool operator < (const Node& x, const Node& y){
 31     if(fabs(x.x - y.x) < eps) return x.y + eps < y.y;
 32     return x.x + eps < y.x;
 33 }
 34 
 35 inline double cross(Node x, Node y){
 36     return x.x * y.y - x.y * y.x;
 37 }
 38 
 39 inline double dis(Node x, Node y){
 40     return sqrt((y.x - x.x) * (y.x - x.x) 
 41      + (y.y - x.y) * (y.y - x.y));
 42 }
 43 
 44 Node next(Node x){
 45     set<Node> :: iterator it;
 46     it = st.upper_bound(x);
 47     if(it != st.end()) return *it;
 48     else return nl;
 49 }
 50 
 51 Node prev(Node x){
 52     set<Node> :: iterator it;
 53     it = st.lower_bound(x);
 54     if(it != st.begin()) return *(--it);
 55     else return nl;
 56 }
 57 
 58 inline void Andrew(){
 59     top = 0;
 60     for(int i = 1; i <= m; i++) if(!ask[node[i].id]){
 61         while(top > 1 && cross(stk[top] - stk[top - 1], node[i] - stk[top]) > eps){
 62             ans -= dis(stk[top], stk[top - 1]); 
 63             top--;
 64         }
 65         stk[++top] = node[i];
 66         if(top > 1) ans += dis(stk[top], stk[top - 1]);
 67     }    
 68     for(int i = 1; i <= top; i++)
 69         st.insert(stk[i]);
 70 } 
 71 
 72 inline void init(){
 73     scanf("%d%d%d%d", &n, &cx, &cy, &m);
 74     for(int i = 1; i <= m; i++){
 75         scanf("%lf%lf", &node[i].x, &node[i].y);
 76         node[i].id = i;
 77     }
 78     ++m; node[m] = (Node){m, 0, 0};
 79     ++m; node[m] = (Node){m, 1.0 * n, 0};
 80     ++m; node[m] = (Node){m, 1.0 * cx, 1.0 * cy};
 81     sort(node + 1, node + m + 1);
 82     for(int i = 1; i <= m; i++){
 83         rf[node[i].id] = i;
 84     }
 85     scanf("%d", &qs);
 86     for(int i = 1; i <= qs; i++){
 87         scanf("%d", &q[i].x);
 88         if(q[i].x == 1){
 89             scanf("%d", &q[i].y);
 90             ask[q[i].y] = 1;
 91         }
 92         else {
 93             as++;
 94             q[i].y = as;    
 95         }
 96     }
 97     Andrew();
 98 }
 99 
100 inline void ins(Node x){
101     Node pre = prev(x), pp;
102     Node nxt = next(x), nn;
103     if(cross(x - pre, nxt - x) > eps){
104         return ;
105     }
106     ans -= dis(pre, nxt);
107     while(pre.id != m - 2){
108         pp = prev(pre);
109         if(cross(pre - pp, x - pre) > eps){
110             ans -= dis(pp, pre);
111             st.erase(pre);
112             pre = pp;
113         }
114         else break;
115     }
116     ans += dis(pre, x);
117     while(nxt.id != m - 1){
118         nn = next(nxt);
119         if(cross(nxt - x, nn - nxt) > eps){
120             ans -= dis(nxt, nn);
121             st.erase(nxt);
122             nxt = nn;
123         }
124         else break;
125     }
126     ans += dis(x, nxt);
127     st.insert(x);
128 }
129 
130 int main(){
131     init();
132     for(int i = qs; i >= 1; i--)
133         if(q[i].x == 1)
134             ins(node[rf[q[i].y]]);
135         else 
136             anss[q[i].y] = ans;
137     for(int i = 1; i <= as; i++) printf("%.2lf
", anss[i]);
138     return 0;    
139 }

View Code

附上代码：