sgu277：Heroes(动态凸包)

题目大意：

       动态凸包 ...

分析：

       参见http://www.cnblogs.com/yejinru/p/3156048.html

AC code：

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <string>
#include <sstream>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <ctime>
#define pb push_back
#define mp make_pair
typedef long long LL;
typedef double DB;
typedef long double LD;
using namespace std;

struct pot
{
    LL x, y;
    DB angle;
    pot() {x = y = angle = ;}
    pot(LL _x, LL _y, DB _angle):x(_x),y(_y),angle(_angle){}
    void read() {scanf("%I64d%I64d", &x, &y);}
    friend bool operator < (const pot &a, const pot &b) {return a.angle < b.angle;}
    friend pot operator * (const pot &a, DB k) {return pot(a.x*k,a.y*k,a.angle);}
    friend pot operator / (const pot &a, DB k) {return pot(a.x/k,a.y/k,a.angle);}
    friend pot operator + (const pot &a, const pot &b) {return pot(a.x+b.x, a.y+b.y, );}
    friend pot operator - (const pot &a, const pot &b) {return pot(a.x-b.x, a.y-b.y, );}
    friend LL operator ^ (const pot &a, const pot &b) {return a.x*b.y-a.y*b.x;} 
}src[];
set<pot> s;
LL ans;

LL det(const pot &a, const pot &b, const pot &c)
{
    return (b-a)^(c-a);
}

pot pre(const pot &p)
{
    set<pot>::iterator it = s.lower_bound(p);
    if(it == s.begin()) it = s.end();
    return *(--it);
}

pot bac(const pot &p)
{
    set<pot>::iterator it = s.upper_bound(p);
    if(it == s.end()) it = s.begin();
    return *it;
}

bool inside(const pot &p)
{
    pot a = pre(p);
    pot b = bac(p);
    return det(p, a, b) >= ;
}

void add(const pot &p)
{
    if(inside(p) || s.count(p)) return ;
    pot a = pre(p), aa, b = bac(p), bb;
    ans += abs(det(p, a, b));
    while(true)
    {
        s.erase(a);
        aa = pre(p);
        if(det(p, a, aa) <= )
        {
            s.insert(a);
            break;
        }
        ans += abs(det(p, a, aa));
        a = aa;
    }
    while(true)
    {
        s.erase(b);
        bb = bac(p);
        if(det(p, b, bb) >= )
        {
            s.insert(b);
            break;
        }
        ans += abs(det(p, b, bb));
        b = bb;
    }
    s.insert(p);
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    int sum = ;
    DB ox = , oy = ;
    srand((unsigned)time(NULL));
    for(int i = ; i < ; ++i)
    {
        src[i].read();
        int k = rand()%;
        ox += src[i].x*k;
        oy += src[i].y*k;
        sum += k;
    }
    ox /= sum, oy /= sum;
    for(int i = ; i < ; ++i)
        s.insert(pot(src[i].x, src[i].y, atan2(src[i].y-oy, src[i].x-ox)));
    ans += abs(det(src[], src[], src[]));

    int n;
    scanf("%d", &n);
    while(n--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(pot(x, y, atan2(y-oy, x-ox)));
        printf("%I64d\n", ans);
    }

    #ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    #endif
    return ;
}