Pagini recente » Istoria paginii utilizator/annem | Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3305018)
// Ilie "The-Winner" Dumitru
// Dumnezeu sa o ierte
#include<bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define err(...) fprintf(stderr, __VA_ARGS__)
using ll=long long;
constexpr int NMAX=801;
constexpr ll MOD=1000000007;
struct pct
{
int x, y;
};
int N, M;
pct poli[801];
int sgn(ll x)
{
return (x>0)-(x<0);
}
ll cross(pct a, pct b, pct c)
{
return b.x*(ll)(c.y-a.y)+c.x*(ll)(a.y-b.y)+a.x*(ll)(b.y-c.y);
}
bool ok(pct p)
{
int i, cnt=0;
for(i=0;i<N;++i)
if(std::min(poli[i].y, poli[i+1].y)<p.y && p.y<=std::max(poli[i].y, poli[i+1].y) && sgn(cross(poli[i], poli[i+1], {std::min(poli[i].x, poli[i+1].x)-1, std::min(poli[i].y, poli[i+1].y)}))*sgn(cross(poli[i], poli[i+1], p))<1)
++cnt;
return cnt%2;
}
int main()
{
FILE* f=fopen("poligon.in", "r"), *g=fopen("poligon.out", "w");
int i, ans=0;
pct p;
fscanf(f, "%d%d", &N, &M);
for(i=0;i<N;++i)
fscanf(f, "%d%d", &poli[i].x, &poli[i].y);
poli[N]=poli[0];
for(i=0;i<M;++i)
{
fscanf(f, "%d%d", &p.x, &p.y);
if(ok(p))
++ans;
}
fprintf(g, "%d\n", ans);
fclose(f);
fclose(g);
return 0;
}