CodeForces 70D Professor's task(动态凸包)

Description:

Once a walrus professor Plato asked his programming students to perform the following practical task.
The students had to implement such a data structure that would support a convex hull on some set of points S. The input to the program had q queries of two types:

1. Add a point with coordinates (x, y) into the set S. Note that in this case the convex hull of S could have changed, and could have remained the same.
2. Say whether a point with coordinates (x, y) belongs to an area limited by the convex hull, including the border.
   All the students coped with the task. What about you?

Input:

The first line contains an integer q (4 ≤ q ≤ 105).
Then follow q lines in the following way: “t x y”, where t is the query type (1 or 2), and (x, y) are the coordinates of the point ( - 106 ≤ x, y ≤ 106, x and y are integers).
There is at least one query of type 2.
It is guaranteed that the three queries of the first type follow first and the points given in the queries form a non-degenerative triangle. Also all the points added in S are distinct.

Output

For each query of the second type print one string containing “YES”, if the point lies inside the convex hull or on its border. Otherwise, print “NO”.

Sample Input:

8
1 0 0
1 2 0
1 2 2
2 1 0
1 0 2
2 1 1
2 2 1
2 20 -1

Sample Output:

YES
YES
YES
NO

题目链接

有凸包集 $s$s ，两种操作

1. 1 x y 向凸包集内添加一个点 $(x,y)$(x,y)
2. 2 x y 询问点 $(x,y)$(x,y) 是否在凸包集 $s$s 的凸包内部（包含边界）

题目保证至少有一次询问，且前三次操作均为 $1$1 插入操作（三点构成不退化三角形）

$1$1 的插入操作有三种情况

如图，当前凸包集 $s$s 为 $\{A,B,D,E,C\}${A,B,D,E,C}

1. 若向 $s$s 内添加点 $F$F ，由于 $F$F 已经在凸包内部，所以不用添加
2. 若向 $s$s 内添加点 $G$G ，由于 $G$G 不影响凸包其它点的构成，直接添加即可
3. 若向 $s$s 内添加点 $H$H ，由于 $H$H 添加后点 $B$B 就不属于凸包集凸包上的构成点，所以需要删除点 $B$B

所以添加操作中需要定位新加点在凸包集凸包中的位置， $GrahamScan$GrahamScan 算法中的极角排序是一种排序定位的方法，但是 $GrahamScan$GrahamScan 算法中的极角排序需要首先找到一定在凸包上的一点（一般是点集中最左下角的点），显然这里的点是未知且需要动态更新的，所以考虑另一种极角排序，首先明确凸包在动态更新中是一定递增（不会缩小）的，所以初始凸包内一点一定一直在凸包内部，之后找到一定在凸包内部的一点（由于题目保证前三次操作均为 $1$1 插入操作，所以可以利用此三点构成三角形的重心为基准点），将凸包集中的点按照极角进行排序（这里我使用了 $atan2$atan2 计算角度，当然也可以不用）

这是如果我们进行 $1$1 插入操作需要在极角序内找到此点的前驱、后继相继判断是否满足凸包的性质（这里的判断直接利用叉积即可），把不满足凸包性质的点进行删除

而查找前驱（后继）、删除的操作需要用到平衡树进行维护

但这里的查找前驱（后继）、删除的操作也可以用 $set$set 进行简单的实现，需要注意的地方是凸包为环状，所以需要手写 $prev、next$prev、next 函数查找极角序内前驱后继

AC代码:

#include <bits/stdc++.h>
using namespace std;

typedef double db;
const int maxn = 1e5 + 5;
const db eps = 1e-9;

int Sgn(db Key) {return fabs(Key) < eps ? 0 : (Key < 0 ? -1 : 1);}
int Cmp(db Key1, db Key2) {return Sgn(Key1 - Key2);}
struct Point {db X, Y;};
typedef Point Vector;
Vector operator - (Vector Key1, Vector Key2) {return (Vector){Key1.X - Key2.X, Key1.Y - Key2.Y};}
Vector operator + (Vector Key1, Vector Key2) {return (Vector){Key1.X + Key2.X, Key1.Y + Key2.Y};}
db operator * (Vector Key1, Vector Key2) {return Key1.X * Key2.X + Key1.Y * Key2.Y;}
db operator ^ (Vector Key1, Vector Key2) {return Key1.X * Key2.Y - Key1.Y * Key2.X;}
db GetLen(Vector Key) {return sqrt(Key * Key);}

int N;
Point Basic;
Point points[maxn];
set<Point> S;

bool operator < (Point Key1, Point Key2) {
    Key1 = Key1 - Basic; Key2 = Key2 - Basic;
    db Ang1 = atan2(Key1.Y, Key1.X), Ang2 = atan2(Key2.Y, Key2.X);
    db Len1 = GetLen(Key1), Len2 = GetLen(Key2);
    if (Cmp(Ang1, Ang2) != 0) return Cmp(Ang1, Ang2) < 0;
    return Cmp(Len1, Len2) < 0;
}

set<Point>::iterator Prev(set<Point>::iterator Key) {
    if (Key == S.begin()) Key = S.end();
    return --Key;
}

set<Point>::iterator Next(set<Point>::iterator Key) {
    ++Key;
    return Key == S.end() ? S.begin() : Key;
}

bool Query(Point Key) {
    set<Point>::iterator it = S.lower_bound(Key);
    if (it == S.end()) it = S.begin();
    return Sgn((Key - *(Prev(it))) ^ (*(it) - *(Prev(it)))) <= 0;
}

void Insert(Point Key) {
    if (Query(Key)) return;
    S.insert(Key);
    set<Point>::iterator Cur = Next(S.find(Key));
    while (S.size() > 3 && Sgn((Key - *(Next(Cur))) ^ (*(Cur) - *(Next(Cur)))) <= 0) {
        S.erase(Cur);
        Cur = Next(S.find(Key));
    }
    Cur = Prev(S.find(Key));
    while (S.size() > 3 && Sgn((Key - *(Cur)) ^ (*(Cur) - *(Prev(Cur)))) >= 0) {
        S.erase(Cur);
        Cur = Prev(S.find(Key));
    }
}

int main(int argc, char *argv[]) {
    scanf("%d", &N);
    Basic.X = Basic.Y = 0.0;
    for (int i = 1, T; i <= 3; ++i) {
        scanf("%d%lf%lf", &T, &points[i].X, &points[i].Y);
        Basic.X += points[i].X; Basic.Y += points[i].Y;
    }
    Basic.X /= 3.0; Basic.Y /= 3.0;
    for (int i = 1; i <= 3; ++i) S.insert(points[i]);
    for (int i = 4, T; i <= N; ++i) {
        scanf("%d%lf%lf", &T, &points[i].X, &points[i].Y);
        if (T == 1) Insert(points[i]);
        else {
            if (Query(points[i])) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}