给一个点集, 除了(0,0)和(n,0), 其他点的横纵坐标均是[1,n-1]内的整数. q个操作: - 询问上凸壳的长度, 精确到小数点后2位. - 删除一个点.
保证(0,0), (n,0)和(x,y)不被删除, 且没有重点. (点数≤10^5+3, q≤2*10^5, n>1) 为了写斜率优化, 先练一练动态加点的凸壳.
离线, 倒过来处理, 变删除为加入.
不像斜率优化里需要对斜率二分查找, 本题只需要维护凸壳, 顺便维护长度, 因此可以直接用stl::set. 然而出于练习的目的码了一发Splay. CDQ说她的Splay有6KB, 现在我信了......
我对每个点记录: 坐标, 与前驱, 后继的距离和连线的斜率. Splay需要支持插入, 查询前驱, 后继. 没写特定的删除函数, splay后直接修改指针.
加点的时候先按横坐标插入. 如果该点在原凸包内, 删除之. 否则, 向左右两边做Graham-scan式的更新.
Splay里的点排序, 应以横坐标为第一关键字, 纵坐标为第二关键字, 正如水平序Graham算法所做的那样.
const int N = 1e5 + 3, MAX_Q = 2e5;
const double Zero = 0, inf = 1.0/Zero;
template<typename T>
inline T square(const T& x)
{
return x * x;
}
struct Point {
int x, y;
Point(int x=-1, int y=-1): x(x), y(y) {}
Point operator-(const Point& o) const
{
return Point(x-o.x, y-o.y);
}
bool operator<(const Point& o) const
{
return x < o.x || (x == o.x && y < o.y);
}
friend int cross(const Point& a, const Point& b)
{
return a.x * b.y - a.y * b.x;
}
friend double dist(const Point& a, const Point& b)
{
return sqrt(square(a.x - b.x) + square(a.y - b.y));
}
friend double slope(const Point& a, const Point& b)
{
return (double)(a.y - b.y) / (a.x - b.x);
}
} P[N];
namespace Splay {
struct Node {
Point p;
double k[2], l[2];
int t;
Node* fa, * ch[2];
Node(int=-1, int=-1);
void* operator new(size_t);
void setf(Node*, int);
} *root, nodes[N + 1], * nil = nodes;
Node::Node(int x, int y): p(x,y), t(-1), fa(0)
{
ch[0] = ch[1] = nil;
}
void* Node::operator new(size_t)
{
static Node* ptr = nodes + 1;
return ptr++;
}
inline void Node::setf(Node* f, int t1)
{
t = t1;
fa = f;
t >= 0 ? f->ch[t] = this : root = this;
}
inline void rot(Node* y)
{
int t = y->t;
Node* x = y->fa;
y->setf(x->fa, x->t);
y->ch[t^1]->setf(x, t);
x->setf(y, t^1);
}
void splay(Node* x, Node* r=0)
{
Node* y;
while ((y = x->fa) != r) {
if (y->fa != r)
rot(y->t ^ x->t ? x : y);
rot(x);
}
}
Node* walk(Node* x, int d)
{
Node* y = x->ch[d];
while (y->ch[d^1] != nil) y = y->ch[d^1];
if (y != nil) splay(y, x);
return y;
}
void insert(Node* x)
{
Node* y = root;
while (true) {
if (y->p < x->p) {
if (y->ch[1] == nil) {
x->setf(y, 1);
break;
} else y = y->ch[1];
} else {
if (y->ch[0] == nil) {
x->setf(y, 0);
break;
} else y = y->ch[0];
}
}
splay(x);
}
}
namespace Convex_Hull {
using namespace Splay;
double length;
void init(int n)
{
root = new Node(0, 0);
Node* t = new Node(n, 0);
root->k[0] = inf, root->k[1] = 0;
t->k[0] = 0, t->k[1] = -inf;
length = root->l[1] = t->l[0] = n;
t->setf(root, 1);
}
void process(Node* a, Node* b, int d)
{
while (b->k[d] == (a->k[d] = slope(a->p, b->p)) || ((a->k[d] < b->k[d]) == d)) {
length -= b->l[d];
Node* t = walk(b, d);
t->setf(a, d);
b = t;
}
length += a->l[d] = b->l[d^1] = dist(a->p, b->p);
b->k[d^1] = a->k[d];
}
void add(int x, int y)
{
Node* a = new Node(x, y);
insert(a);
Node* l = walk(a, 0), * r = walk(a, 1);
if (cross(a->p - l->p, r->p - l->p) >= 0) {
l->setf(0, -1);
r->setf(l, 1);
return;
}
length -= l->l[1];
process(a, l, 0);
process(a, r, 1);
}
}
pair<int, int> Q[MAX_Q];
bool cancel[N];
double ans[MAX_Q];
int main()
{
using namespace Convex_Hull;
int n, x, y, m, q;
scanf("%d%d%d%d", &n, &x, &y, &m);
init(n);
add(x, y);
Rep (i, 0, m) scanf("%d%d", &P[i].x, &P[i].y);
scanf("%d", &q);
Rep (i, 0, q) {
scanf("%d", &Q[i].first);
if (Q[i].first == 1) {
scanf("%d", &Q[i].second);
cancel[--Q[i].second] = true;
}
}
Rep (i, 0, m)
if (!cancel[i]) add(P[i].x, P[i].y);
Down (i, q-1, 0) {
if (Q[i].first == 2)
ans[i] = length;
else {
int t = Q[i].second;
add(P[t].x, P[t].y);
}
}
Rep (i, 0, q)
if (ans[i])
printf("%.2f\n", ans[i]);
return 0;
}