Pagini recente » Cod sursa (job #379787) | Cod sursa (job #1025623) | Cod sursa (job #240704) | Cod sursa (job #448316) | Cod sursa (job #3300276)
#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;
if (y1 <= y && y <= y2) /// se intersecteaza, dar nu stim daca in stanga sau dreapta
{
// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << x * (y1 - y2) << endl;
if ((y1*x2 - x1*y2 - y * (x2 - x1)) / (y1 - y2) <= x) /// 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;
}