补昨天的题。
比较好想的计算几何。就看每个点在不在另一个颜色的点形成的上凸壳下面，下凸壳上面。这个用二分可以做到单次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);
}