Pagini recente » Cod sursa (job #1091969) | Cod sursa (job #762404) | Cod sursa (job #2434312) | Cod sursa (job #2292659) | Cod sursa (job #2148815)
#include <iostream>
#include <fstream>
#include <cmath>
#define exterior -1
#define pe_latura 0
#define interior 1
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
const int maxn = 805;
const double EPS = 1e-10;
int N, m;
struct punct
{
double x, y;
};
punct P[maxn], M;
int int_pe_ext()
{
int i, intersectii = 0;
P[N + 1] = P[1];
P[N + 2] = P[2];
for(i = 1; i <= N; i++)
{
if((P[i].x < M.x && M.x < P[i + 1].x) || (P[i].x > M.x && M.x > P[i + 1].x))
{
double cy = P[i].y + (M.x - P[i].x) * (P[i].y - P[i + 1].y) / (P[i].x - P[i + 1].x);
if(abs(M.y - cy) < EPS) return pe_latura;
else
if(M.y > cy) intersectii++;
continue;
}
if(P[i].x == M.x)
{
if(P[i].y == M.y)
return pe_latura;
if((P[i+1].x ==M.x) && ((P[i].y <= M.y && M.y <= P[i + 1].y) || (P[i].y >= M.y && M.y >= P[i + 1].y)))
return pe_latura;
}
if(P[i].x == M.x && P[i].y <= M.y)
{
if(P[i + 1].x == M.x)
{
if(M.y <= P[i + 1].y)
return pe_latura;
else
if((P[i - 1].x - M.x) * (P[i + 2].x - M.x) <= 0)
intersectii++;
}
else
{
if((P[i - 1].x - M.x) * (P[i + 1].x - M.x) < 0)
intersectii++;
}
}
}
if(intersectii % 2 == 1) return interior;
return exterior;
}
int main()
{
int ans=0;
f >> N >> m;
for(int i = 1; i <= N; i++)
f >> P[i].x >> P[i].y;
for(int i = 1; i <= m; i++)
{
f >> M.x >> M.y;
if(int_pe_ext() >= 0) ans++;
}
g<<ans<<'\n';
return 0;
}