Pagini recente » Cod sursa (job #3004520) | Cod sursa (job #3267498) | Cod sursa (job #239351) | Cod sursa (job #952142) | Cod sursa (job #2734683)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
struct punct
{
int x, y;
//vector<int> vec;
bool operator<(const punct other) const
{
return x < other.x;
}
} poli[805];
int n, m;
void read()
{
f>>n>>m;
for(int i = 0; i<n; i++)
{
f>>poli[i].x>>poli[i].y;
/*poli[i].vec.push_back((i-1+n)%n);
poli[i].vec.push_back((i+1)%n);*/
}
//sort(poli, poli+n);
}
int directie(punct a, punct b, punct c)
{
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
int sign(int val)
{
return val < 0 ? -1 : 1;
}
int verifIntersectie(punct D1P1, punct D1P2, punct D2P1, punct D2P2)
{
if(sign(directie(D1P1, D1P2, D2P1)) != sign(directie(D1P1, D1P2, D2P2)) && sign(directie(D2P1, D2P2, D1P1)) != sign(directie(D2P1, D2P2, D1P2)))
return 1;
return 0;
}
bool pctIntrePcte(punct pct, punct p1, punct p2)
{
if(p1.x > p2.x)
swap(p1.x, p2.x);
if(p1.y > p2.y)
swap(p1.y, p2.y);
return p1.x <= pct.x && pct.x <= p2.x && p1.y <= pct.y && pct.y <= p2.y;
}
/*int parc(punct *start; punct *stop)
{
for(punct *itr = start; itr != stop; itr++)
{
verifIntersectie()
}
}*/
int intersectii(punct pct)
{
int nrInt = 0;
if(directie(poli[n-1], poli[0], pct) == 0 && pctIntrePcte(pct, poli[n-1], poli[0]))
return 1;
nrInt += verifIntersectie(poli[n-1], poli[0], pct, {100000, pct.y});
for(int i = 0; i<n-1; i++)
{
if(directie(poli[i], poli[i+1], pct) == 0 && pctIntrePcte(pct, poli[i], poli[i+1]))
return 1;
nrInt += verifIntersectie(poli[i], poli[i+1], pct, {100000, pct.y});
}
return nrInt;
}
void solve()
{
int nrPcte = 0;
punct pct;
for(int i = 0; i<m; i++)
{
f>>pct.x>>pct.y;
/*auto pos = upper_bound(poli, poli+n, pct);*/
/*if(pos - poli <= n/2)
parc(poli, pos+1);
else
parc(pos, poli+n);*/
if((intersectii(pct)&1) == 1)
nrPcte++;
}
g<<nrPcte;
}
int main()
{
read();
solve();
return 0;
}