Cod sursa(job #3305020)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 29 iulie 2025 15:17:48
Problema Poligon Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 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[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);
	c.x-=a.x;
	c.y-=a.y;
	b.x-=a.x;
	b.y-=a.y;
	return c.x*(ll)b.y-c.y*(ll)b.x;
}

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;
}