laekov

补昨天的题。

比较好想的计算几何。就看每个点在不在另一个颜色的点形成的上凸壳下面，下凸壳上面。这个用二分可以做到单次log。用单调应该也能O(n)。

但是写起来非常坑，要用long long，还有各种等号啥的。

写win32 app来显示点的代码比交上去的代码还长。开心。

    

#include <cstdio>

#include <algorithm>

 

usingnamespacestd;

 

typedeflonglongqw;

 

#define _l (qw)

 

structpoint {

    intx, y;

    point (intx0 = 0, inty0 = 0) {

        x = x0, y = y0;

    }

    inlinevoidread() {

        scanf("%d%d", &x, &y);

    }

};

structvect {

    intx, y;

    vect(intx0 = 0, inty0 = 0) {

        x = x0, y = y0;

    }

    vect(constpoint& a, constpoint& b) {

        x = b. x - a. x, y = b. y - a. y;

    }

    inlineqw mulx(constvect& a) const{

        return_l x * a. y - _l y * a. x;

    }

};

 

inlineboolcmpPoint(constpoint& a, constpoint& b) {

    returna. x < b. x || (a. x == b. x && a. y < b. y);

}

 

constintmaxn = 50009;

 

intn, l[maxn], q[maxn], t;

point a[maxn], b[maxn];

 

qw direc(point d) {

    if(d. x > b[q[t]]. x || d. x < b[q[1]]. x)

        return-1;

    intl = 1, r = t - 1;

    while(l < r) {

        intmid = (l + r + 1) >> 1;

        if(b[q[mid]]. x < d. x)

            l = mid;

        else

            r = mid - 1;

    }

    if(d. x == b[q[l]]. x && b[q[l]]. x == b[q[l + 1]]. x) {

        if(d. y >= b[q[l]]. y && d. y <= b[q[l + 1]]. y)

            return0;

        elseif(d. y <= b[q[l]]. y)

            return-1;

        else

            return1;

    }

    else

        returnvect(b[q[l]], b[q[l + 1]]). mulx(vect(b[q[l]], d));

}

 

intcalc() {

    ints = 0;

    for(inti = 0; i < n; ++ i)

        l[i] = 0;

    t = 1;

    q[1] = 0;

    for(inti = 1; i < n; ++ i) {

        while(t > 1 && vect(b[q[t - 1]], b[q[t]]). mulx(vect(b[q[t]], b[i])) <= 0)

            -- t;

        q[++ t] = i;

    }

    for(inti = 0; i < n; ++ i)

        if(direc(a[i]) >= 0)

            ++ l[i];

    t = 1;

    q[1] = 0;

    for(inti = 1; i < n; ++ i) {

        while(t > 1 && vect(b[q[t - 1]], b[q[t]]). mulx(vect(b[q[t]], b[i])) >= 0)

            -- t;

        q[++ t] = i;

    }

    for(inti = 0; i < n; ++ i)

        if(direc(a[i]) <= 0)

            ++ l[i];

    for(inti = 0; i < n; ++ i)

       if(l[i] == 2 && a[i]. x >= b[0]. x && a[i]. x <= b[n - 1]. x)

         ++ s;  

    returns;

}

 

intmain() {

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

#endif

 

    scanf("%d", &n);

    for(inti = 0; i < n; ++ i)

        a[i]. read();

    for(inti = 0; i < n; ++ i)

        b[i]. read();

    sort(a, a + n, cmpPoint);

    sort(b, b + n, cmpPoint);

    intansa = calc();

    for(inti = 0; i < n; ++ i)

        swap(a[i], b[i]);

    intansb = calc();

    printf("%d %d\n", ansb, ansa);

}