Mai intai trebuie sa te autentifici.
Cod sursa(job #781648)
Utilizator | Data | 24 august 2012 19:46:16 | |
---|---|---|---|
Problema | Poligon | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.35 kb |
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define MAXN 802
#define EPS 1e-8
#define MAXM 60010
#define point pair<double, double>
#define INFINITY make_pair(-1.0, -1.0)
#define x first
#define y second
point A[MAXN];
point B[MAXM];
double V[MAXN];
point V1[MAXN], V2[MAXN];
int Ind[MAXN];
int i, j, nr, poz;
int N, M;
point X, Y, Z, T;
double semn;
int st, dr, mij, sol;
int Ans;
inline double det(const point &A, const point &B, const point &C)
{
return (A.x * B.y + B.x * C.y + C.x * A.y - A.y * B.x - B.y * C.x - C.y * A.x);
}
inline int cmp_real(const double &a, const double &b)
{
if (a+EPS < b) return -1;
if (b+EPS < a) return 1;
return 0;
}
inline point intersect(const point &A, const point &B, const point &C, const point &D)
{
double x1, x2, x3, x4, y1, y2, y3, y4, q, w, e;
x1 = A.x; x2 = B.x; x3 = C.x; x4 = D.x;
y1 = A.y; y2 = B.y; y3 = C.y; y4 = D.y;
e = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
if (cmp_real(0.0, e) == 0)
return INFINITY;
q = (x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - x4 * y3);
w = (x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - x4 * y3);
q = q / e;
w = w / e;
return make_pair(q, w);
}
inline bool OnSegment(point A, point B, point C)
{
if (cmp_real(A.x, B.x) == 1)
swap(A, B);
if (cmp_real(C.x, A.x) == -1) return false;
if (cmp_real(B.x, C.x) == -1) return false;
return true;
}
inline bool cmp(const point &q, const point &w)
{
return (cmp_real(q.y, w.y) < 0);
}
inline point rotation(const point &A, const double angle)
{
double X, Y;
X = A.x * cos(angle) - A.y * sin(angle);
Y = A.x * sin(angle) + A.y * cos(angle);
return make_pair(X, Y);
}
int main()
{
freopen("poligon.in","r",stdin);
freopen("poligon.out","w",stdout);
scanf("%d %d",&N, &M);
for (i = 1; i <= N; ++i){
scanf("%lf %lf",&A[i].x, &A[i].y);
A[i] = rotation(A[i], 0.000);
V[i] = A[i].x;
}
A[N+1] = A[1];
for (i = 1; i <= M; ++i){
scanf("%lf %lf", &B[i].x, &B[i].y);
B[i] = rotation(B[i], 0.000);
}
sort(B+1, B+M+1);
sort(V+1, V+N+1);
poz = 1;
for (i = 1; i < N; ++i){
if (cmp_real(V[i], V[i+1]) == 0) continue;
X = make_pair(V[i], -1.0);
Y = make_pair(V[i+1], -1.0);
Z = make_pair(V[i+1], 60001.0);
T = make_pair(V[i], 60001.0);
nr = 0;
for (j = 1; j <= N; ++j){
V1[++nr] = intersect(X, T, A[j], A[j+1]);
if (V1[nr] == INFINITY) {
--nr;
continue;
}
V2[nr] = intersect(Y, Z, A[j], A[j+1]);
if (V2[nr] == INFINITY){
--nr;
continue;
}
if (OnSegment(A[j], A[j+1], V1[nr]) == false){
--nr;
continue;
}
if (OnSegment(A[j], A[j+1], V2[nr]) == false){
--nr;
continue;
}
}
for (j = 1; j <= nr; ++j)
Ind[j] = j;
sort(V1+1, V1+nr+1, cmp);
sort(V2+1, V2+nr+1, cmp);
while (poz <= M && cmp_real(B[poz].x, V[i+1]) < 0){
sol = 0;
st = 1 << 9;
for (sol = 0; st; st >>=1)
if (sol + st <= nr && cmp_real(det(V1[sol+st], V2[sol+st], B[poz]), 0.0) >= 0)
sol |= st;
if (sol == 0){
++poz;
continue;
}
semn = det(V1[sol], V2[sol], B[poz]);
if (cmp_real(semn, 0.0) == 0){
++Ans;
++poz;
continue;
}
if (sol % 2 == 1)
++Ans;
++poz;
}
}
printf("%d\n", Ans);
return 0;
}