Pagini recente » Cod sursa (job #435497) | Cod sursa (job #2806996) | Cod sursa (job #2255904) | Borderou de evaluare (job #1877029) | Cod sursa (job #3300287)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
typedef long long ll;
typedef long double ld;
const int N = 805;
struct
{
int x1, y1, x2, y2;
} v[N];
pair<int, int> f[N];
int n, m, x, y, rasp;
/**
1 x1 y1
1 x2 y2
1 x y
1 x1 y1
1 x2 y2
y(x2 - x1) + x(y1 - y2) = y1*x2 - x1*y2
x(y1 - y2) = y1*x2 - x1*y2 - y(x2 - x1)
x = (y1*x2 - x1*y2 - y(x2 - x1)) / (y1 - y2)
(y1*x2 - x1*y2 - y(x2 - x1)) <= x * (y1 - y2)
*/
bool valid()
{
/// ray_cast in stanga
int x1, y1, x2, y2;
int nr = 0;
for (int i = 1; i <= n; i++)
{
x1 = v[i].x1;
y1 = v[i].y1;
x2 = v[i].x2;
y2 = v[i].y2;
/// verificam daca e pe linie
if (min(y1, y2) <= y && y <= max(y1, y2)) /// se intersecteaza, dar nu stim daca in stanga sau dreapta
{
if ((1ll * y1*x2 - 1ll * x1*y2 - 1ll * y*(x2 - x1)) == 1ll * x * (y1 - y2))
return 1;
if (y1 == y2)
continue;
if ((y1 - y2 > 0) && ((1ll * y1*x2 - 1ll * x1*y2 - 1ll * y * (x2 - x1)) < 1ll * x * (y1 - y2))) /// e in stanga
nr++;
else if ((y1 - y2 < 0) && ((1ll * y1*x2 - 1ll * x1*y2 - 1ll * y * (x2 - x1)) > 1ll * x * (y1 - y2))) /// e in stanga
nr++;
}
}
return nr % 2 == 1;
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= n; i++)
fin >> f[i].first >> f[i].second;
v[1] = {f[1].first, f[1].second, f[n].first, f[n].second};
for (int i = 2; i <= n; i++)
v[i] = {f[i - 1].first, f[i - 1].second, f[i].first, f[i].second};
while (m--)
{
fin >> x >> y;
if (valid())
rasp++;
}
fout << rasp << '\n';
fin.close();
fout.close();
return 0;
}