Cod sursa(job #3305028)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 29 iulie 2025 15:31:51
Problema Poligon Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
// 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 && sgnCrs[i]*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<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;
}