织梦网站关掉wap,品牌建设让,淄博网站制作优化,长春网站设计哪家好【BZOJ2300】[HAOI2011]防线修建 Description 近来A国和B国的矛盾激化#xff0c;为了预防不测#xff0c;A国准备修建一条长长的防线#xff0c;当然修建防线的话#xff0c;肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决#xff0c;到底该把哪些城市…【BZOJ2300】[HAOI2011]防线修建 Description 近来A国和B国的矛盾激化为了预防不测A国准备修建一条长长的防线当然修建防线的话肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决到底该把哪些城市作为保护对象呢又由于A国的经费有限所以希望你能帮忙完成如下的一个任务 1.给出你所有的A国城市坐标 2.A国上层经过讨论考虑到经济问题决定取消对i城市的保护也就是说i城市不需要在防线内了 3.A国上层询问对于剩下要保护的城市修建防线的总经费最少是多少 你需要对每次询问作出回答。注意单位1长度的防线花费为1。 A国的地形是这样的形如下图x轴是一条河流相当于一条天然防线不需要你再修建 A国总是有两个城市在河边一个点是(0,0)一个点是(n,0)其余所有点的横坐标均大于0小于n纵坐标均大于0。A国有一个不在(0,0)和(n,0)的首都。(0,0),(n,0)和首都这三个城市是一定需要保护的。 上图中A,B,C,D,E点为A国城市且目前都要保护那么修建的防线就会是A-B-C-D花费也就是线段AB的长度线段BC的长度线段CD的长度,如果这个时候撤销B点的保护那么防线变成下图 Input 第一行三个整数n,x,y分别表示河边城市和首都是(0,0)(n,0)(x,y)。 第二行一个整数m。 接下来m行每行两个整数a,b表示A国的一个非首都非河边城市的坐标为(a,b)。 再接下来一个整数q表示修改和询问总数。 接下来q行每行要么形如1 i要么形如2分别表示撤销第i个城市的保护和询问。 Output 对于每个询问输出1行一个实数v表示修建防线的花费保留两位小数 Sample Input 4 2 1 2 1 2 3 2 5 2 1 1 2 1 2 2 Sample Output 6.47 5.84 4.47 HINT m100000,q200000,n1 所有点的坐标范围均在10000以内, 数据保证没有重点 题解容易想到离线然后本题就变成了加点和维护凸包可以用平衡树来维护凸包来搞以前一直以为必须用Splay结果发现好像set就行。 具体地我们在set中的点是按x值从小到大排序的。在加入一个点时先找到凸包中它的前驱和后继节点用叉积判一下当前点是否已经在凸包里面。如果在则不用加点否则加入当前点并不断执行以下操作 如果当前点和左侧两个点形成的不是上凸包则将当前点的前驱删掉否则退出。 右面同理。 然后就做完了细节也不是特别多。 #include cstdio
#include cstring
#include iostream
#include algorithm
#include set
#include cmath
using namespace std;
const int maxn200010;
struct point
{int x,y;point() {}point(int a,int b) {xa,yb;}bool operator ! (const point a) const {return (x!a.x)||(y!a.y);}bool operator (const point a) const {return (xa.x)?(ya.y):(xa.x);}point operator - (const point a) const {return point (x-a.x,y-a.y);}int operator * (const point a) const {return x*a.y-y*a.x;}
}p[maxn];
double dis(const point a,const point b) {return sqrt((a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y));}
setpoint s;
setpoint::iterator it;
double ans;
int n,m,q;
int del[maxn],op[maxn],qi[maxn];
double qa[maxn];
inline int rd()
{int ret0,f1; char gcgetchar();while(gc0||gc9) {if(gc-) f-f; gcgetchar();}while(gc0gc9) retret*10(gc^0),gcgetchar();return ret*f;
}
inline void add(point x)
{point a,b,c;its.upper_bound(x),b*it,it--,a*it;if(x.xb.x) return ;if((x-a)*(b-x)0) return ;ans-dis(a,b);while(a!point(0,0)){it--,c*it;if((a-c)*(x-a)0) ans-dis(a,c),s.erase(s.find(a)),ac;else break;}its.find(b);while(b!point(n,0)){it,c*it;if((b-x)*(c-b)0) ans-dis(b,c),s.erase(s.find(b)),bc;else break;}ansdis(a,x)dis(x,b);s.insert(x);
}
int main()
{int i,a,b;nrd(),ard(),brd(),mrd();s.insert(point(0,0)),s.insert(point(n,0)),s.insert(point(a,b));ansdis(point(0,0),point(a,b))dis(point(n,0),point(a,b));for(i1;im;i) p[i].xrd(),p[i].yrd();qrd();for(i1;iq;i){op[i]rd();if(op[i]1) qi[i]rd(),del[qi[i]]1;}for(i1;im;i) if(!del[i]) add(p[i]);for(iq;i1;i--){if(op[i]2) qa[i]ans;else add(p[qi[i]]);}for(i1;iq;i) if(op[i]2) printf(%.2lf\n,qa[i]);return 0;
} 转载于:https://www.cnblogs.com/CQzhangyu/p/7965400.html
