思路:

倒着加显然吧  动态维护这个凸包就好了

//By SiriusRen
#include <bits/stdc++.h>
using namespace std;
const int N=;
int n,m,q,vis[N];
double now;
struct Point{int x,y;}point[N],jy,tmp,tt;
struct Query{int x,op;double ans;}ask[N];
Point operator-(Point a,Point b){
Point c;c.x=a.x-b.x,c.y=a.y-b.y;return c;
}
int operator*(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
bool operator<(Point a,Point b){
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
double dis(Point a,Point b){
a=a-b;return sqrt(a.x*a.x+a.y*a.y);
}
set<Point>s;set<Point>::iterator l,r,t;
void insert(Point a){
r=s.lower_bound(a),l=r,l--;
if((*r-*l)*(a-*l)<)return;
now-=dis((*l),(*r));
s.insert(a),t=r,r++;
while(r!=s.end()&&(*r-a)*(*t-a)<)
now-=dis(*t,*r),s.erase(t),t=r,r++;
while(l!=s.begin()){
t=l,l--;
if((*t-a)*(*l-a)>)break;
now-=dis(*t,*l),s.erase(t);
}
l=r=t=s.find(a),l--,r++;
now+=dis(*l,a)+dis(*r,a);
}
int main(){
s.insert(tt);
scanf("%d%d%d%d",&n,&jy.x,&jy.y,&m);
tmp.x=n;now+=dis(tt,jy)+dis(jy,tmp);
for(int i=;i<=m;i++)
scanf("%d%d",&point[i].x,&point[i].y);
scanf("%d",&q);
for(int i=;i<=q;i++){
scanf("%d",&ask[i].op);
if(ask[i].op==)scanf("%d",&ask[i].x),vis[ask[i].x]=;
}s.insert(jy),s.insert(tmp);
for(int i=;i<=m;i++)if(!vis[i])insert(point[i]);
for(int i=q;i;i--){
if(ask[i].op==)insert(point[ask[i].x]);
else ask[i].ans=now;
}
for(int i=;i<=q;i++)
if(ask[i].op!=)printf("%.2lf\n",ask[i].ans);
}

最新文章

  1. sublime3 的安装
  2. 16-1-26---图解HTTP(01)
  3. 数据库join方式分析
  4. centos7安装activemq
  5. PHP输出控制(Output Control)函数
  6. xUtils,butterknife...处理findviewbyid
  7. RCU-数据库初始化参数
  8. ECshop模板机制
  9. 在Linux下开始C语言的学习
  10. BOM的来源是不可能出现的字符,GB2312双字节高位都是1,Unicode理论的根本缺陷导致UTF8的诞生
  11. ios-王云鹤 调用ios系统功能---------------打电话、发短信、发邮件
  12. Websocket实例
  13. 利用GeneratedKeyHolder获得新增数据主键值
  14. 继BAT之后 第四大巨头是谁
  15. 使用promise手动封装ajax函数
  16. TIJ学习总结(1)- Java基础语法
  17. (转)聊聊Greenplum的那些事
  18. [Python学习笔记] 数字类型及操作
  19. 小程序 official-account
  20. ASP.NET MVC+EF框架+EasyUI实现权限管理(附源码)

热门文章

  1. JDBC在Java Web中的应用
  2. jsonview插件的常见使用方法整理
  3. dual boot
  4. RabbitMQ整合spring----https://www.cnblogs.com/woms/p/7040902.html
  5. rpm 命令的使用
  6. multiple instance of mac app
  7. 洛谷—— P1122 最大子树和
  8. Java AOP 获取HttpSevletRequest、HttpSevletResponse、HttpSession对象
  9. 演练:使用VS2010 C# 创作简单的多线程组件
  10. Lua的面向对象程序设计