Pagini recente » Cod sursa (job #2132637) | Cod sursa (job #2496214) | Cod sursa (job #2262724) | Cod sursa (job #2119926) | Cod sursa (job #2147539)
#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 nr = 0;
for (int i = 1; i <= nL[fasie]; i++)
{
double det = det_arie (pct, L[fasie][i].A, L[fasie][i].B);
if (det == 0) return 1;
if (det > 0) nr++;
}
return nr;
}
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;
}