Pagini recente » Cod sursa (job #1758238) | Cod sursa (job #1088788) | Cod sursa (job #1611431) | Cod sursa (job #542452) | Cod sursa (job #1991097)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
struct punct
{
double x, y;
} p[801];
struct latura
{
punct A, B;
} l[801], L[801][801];
int N, K, nrf, nL[801];
bool cmp(punct A, punct B)
{
if(A.x == B.x) return A.y < B.y;
return A.x < B.x;
}
bool cmpl(latura l1, latura l2)
{
return (l1.A.y + l1.B.y) < (l2.A.y + l2.B.y);
}
double det_arie(punct A, punct B, punct C)
{
return (A.x - B.x) * (B.y - C.y) - (B.x - C.x) * (A.y - B.y);
}
punct intersectie_dr(latura l, double x)
{
punct pct;
pct.x = x;
if(l.A.y == l.B.y) pct.y = l.A.y;
else pct.y = l.A.y - (l.A.x - x) * (l.B.y - l.A.y) / (l.B.x - l.A.x);
return pct;
}
int cautfasie(punct pct)
{
int st = 1, dr = nrf, m;
while(st <= dr)
{
m = st + (dr - st) / 2;
if(pct.x >= p[m].x && pct.x <= p[m + 1].x) return m;
else if(pct.x < p[m].x) dr = m - 1;
else st = m + 1;
}
return m;
}
int nrlatsub(int fasie, punct pct)
{
int st = 1, dr = nL[fasie], m;
if(det_arie(pct, L[fasie][st].A, L[fasie][st].B) < 0) return 0;
if(det_arie(pct, L[fasie][dr].A, L[fasie][dr].B) > 0) return 0;
while(st < dr)
{
m = st + (dr - st + 1) / 2;
if(det_arie(pct, L[fasie][m].A, L[fasie][m].B) > 0) st = m;
else dr = m - 1;
}
return st;
}
bool interior(punct pct)
{
if(pct.x < p[1].x || pct.x > p[nrf].x) return 0;
int fasie = cautfasie(pct);
int latsub = nrlatsub(fasie, pct);
if(latsub % 2 == 1) return 1;
return 0;
}
int main()
{
f >> N >> K;
f >> p[1].x >> p[1].y;
for(int i = 2; i <= N; i++)
{
f >> p[i].x >> p[i].y;
l[i - 1].A = p[i - 1], l[i - 1].B = p[i];
if(cmp(l[i - 1].B, l[i - 1].A)) swap(l[i - 1].A, l[i - 1].B);
}
l[N].A = p[N], l[N].B = p[1];
if(cmp(l[N].B, l[N].A)) swap(l[N].A, l[N].B);
//determinarea fasiilor
sort(p + 1, p + N + 1, cmp);
nrf = 1;
for(int i = 2; i <= N; i++)
if(p[i].x != p[i - 1].x) p[++nrf] = p[i];
//determinarea si sortarea dupa y a laturilor din fiecare fasie
for(int i = 1; i < nrf; i++)
{
nL[i] = 0;
for(int j = 1; j <= N; j++)
if(l[j].A.x <= p[i].x && l[j].B.x >= p[i + 1].x)
{
nL[i]++;
L[i][nL[i]].A = intersectie_dr(l[j], p[i].x);
L[i][nL[i]].B = intersectie_dr(l[j], p[i + 1].x);
}
sort(L[i] + 1, L[i] + nL[i] + 1, cmpl);
}
punct pct;
int sol = 0;
for(int i = 1; i <= K; i++)
{
f >> pct.x >> pct.y;
if(interior(pct)) sol++;
}
g << sol << '\n';
return 0;
}