bzoj2928: [Poi1999]飞弹

惨啊…… 被卡常是一种什么感受&……

很明显的分治。

我们首先可以找到所有点中的最低点，然后对所有点进行一次极角排序，选取一个点使得他各侧飞弹和地堡一样多，并对两侧继续进行分治。

很容易证明这样做的正确性。

然而这样做是\(n^{2}log(n)\)。所以我们需要加些玄学的优化……比如通过增加每次分治的宽度，以减少排序的次数……

……总之就是水过啦QAQ

#include <bits/stdc++.h>

#define N 20010

const int H = ;

char s0[H] , * s1 = s0 , * s2 = s1;

#define I ( s1 == s2 &&( s2 = ( s1 = s0 ) + fread( s0 , 1 , H , stdin ) , s1 == s2 ) ? 32 : * s1++ )

inline int read()

{

    register int x =  , c, f = ;

    while( isspace( c = I ) );

    if (c == '-') f = ; else x = x *  + c - ;

    while(isdigit( c = I ) ) x = x *  + c - ;

    return (f? -x: x);

}

using namespace std;

int n;

struct node

{

    int x, y, t, i;

} L[N];

node O;

int ansi[N];

int ci[N];

int compc(int a, int b)

{

    return ((L[a].x - O.x) * (L[b].y - O.y) - (L[b].x - O.x) * (L[a].y - O.y)) < ;

}

int comp(node a, node b)

{

    return ((a.x - O.x) * (b.y - O.y) - (b.x - O.x) * (a.y - O.y)) < ;

}

void solve(int l, int r)

{

    if (l > r) return;

    for (int i = l + ; i <= r; ++ i)

        if (L[ci[i]].y < L[ci[l]].y) swap(ci[i], ci[l]);

    O = L[ci[l]];

    sort(ci + l + , ci + r + , compc);

    int np = l + ;

    for (int i = l + , k = ; i < r; ++ i)

    {

        k += L[ci[i]].t;

        if (k == )

        {

            solve(np, i);

            np = i + ;

        }

    }

    if (L[ci[l]].t > ) ansi[L[ci[l]].i] = L[ci[np]].i;

    else ansi[L[ci[np]].i] = L[ci[l]].i;

    solve(np + , r);

}

int compi(node a, node b)

{

    if (a.t != b.t) return a.t > b.t;

    else return a.i < b.i;

}

int checker()

{

    sort(L + , L + n *  + , compi);

    for (int i = ; i <= n; ++ i)

        for (int j = ; j <= n; ++ j)

            if (i != j)

            {

                O = L[i];

                int a = comp(L[ansi[i] + n], L[j]) ^ comp(L[ansi[i] + n], L[ansi[j] + n]);

                O = L[j];

                int b = comp(L[ansi[j] + n], L[i]) ^ comp(L[ansi[j] + n], L[ansi[i] + n]);

                if (a && b)

                    return ;

            }

    return ;

}

int main()

{

    //freopen("rak0.in", "r", stdin);

    n = read();

    for (int i = ; i <=  * n; ++ i) ci[i] = i;

    for (int i = ; i <= n; ++ i)

    {

        L[i].x = read(); L[i].y = read();

        L[i].t = ; L[i].i = i;

    }

    for (int i = ; i <= n; ++ i)

    {

        L[i + n].x = read(); L[i + n].y = read();

        L[i + n].t = -; L[i + n].i = i;

    }

    solve(, n * );

    for (int i = ; i <= n; ++ i) printf("%d\n", ansi[i]);

    //printf("%d", checker());

}