Pagini recente » Cod sursa (job #346825) | Cod sursa (job #3312377) | Cod sursa (job #1742346) | Cod sursa (job #3317703) | Cod sursa (job #3305029)
// 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[NMAX];
pct min[NMAX], max[NMAX];
int sgnCrs[NMAX];
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(poli[i].y==poli[i+1].y)
{
if(p.y==poli[i].y && min[i].x<=p.x && p.x<=max[i].x)
return 1;
}
else if(min[i].y<p.y && p.y<=max[i].y)
{
int x=sgnCrs[i]*sgn(cross(poli[i], poli[i+1], p));
if(x==0)
return 1;
if(x==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<N;++i)
{
min[i].x=std::min(poli[i].x, poli[i+1].x);
min[i].y=std::min(poli[i].y, poli[i+1].y);
max[i].x=std::max(poli[i].x, poli[i+1].x);
max[i].y=std::max(poli[i].y, poli[i+1].y);
sgnCrs[i]=sgn(cross(poli[i], poli[i+1], {min[i].x-1, min[i].y}));
}
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;
}