BZOJ 2300凸包+离线
2024-08-30 23:07:22
思路:
倒着加显然吧 动态维护这个凸包就好了
//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);
}
最新文章
- sublime3 的安装
- 16-1-26---图解HTTP(01)
- 数据库join方式分析
- centos7安装activemq
- PHP输出控制(Output Control)函数
- xUtils,butterknife...处理findviewbyid
- RCU-数据库初始化参数
- ECshop模板机制
- 在Linux下开始C语言的学习
- BOM的来源是不可能出现的字符,GB2312双字节高位都是1,Unicode理论的根本缺陷导致UTF8的诞生
- ios-王云鹤 调用ios系统功能---------------打电话、发短信、发邮件
- Websocket实例
- 利用GeneratedKeyHolder获得新增数据主键值
- 继BAT之后 第四大巨头是谁
- 使用promise手动封装ajax函数
- TIJ学习总结(1)- Java基础语法
- (转)聊聊Greenplum的那些事
- [Python学习笔记] 数字类型及操作
- 小程序 official-account
- ASP.NET MVC+EF框架+EasyUI实现权限管理(附源码)
热门文章
- JDBC在Java Web中的应用
- jsonview插件的常见使用方法整理
- dual boot
- RabbitMQ整合spring----https://www.cnblogs.com/woms/p/7040902.html
- rpm 命令的使用
- multiple instance of mac app
- 洛谷—— P1122 最大子树和
- Java AOP 获取HttpSevletRequest、HttpSevletResponse、HttpSession对象
- 演练:使用VS2010 C# 创作简单的多线程组件
- Lua的面向对象程序设计