Pagini recente » Cod sursa (job #1281895) | Cod sursa (job #1721912) | Cod sursa (job #3220367) | Cod sursa (job #1758169) | Cod sursa (job #2410034)
#include <fstream>
#include <vector>
using namespace std;
#define FILE_NAME "poligon"
ifstream in (FILE_NAME".in");
ofstream out(FILE_NAME".out");
typedef long long LL;
struct punct
{
LL x, y;
punct(LL _x = 0, LL _y = 0)
{
x = _x;
y = _y;
}
};
struct segment
{
punct A, B;
segment(punct _A = punct(0, 0), punct _B = punct(0, 0))
{
A = _A;
B = _B;
}
};
vector < segment > Edges;
int N, M;
LL det(punct A, punct B, punct C)
{
return (A.x * B.y + B.x * C.y + C.x * A.y) -
(A.y * B.x + B.y * C.x + C.y * A.x);
}
bool cross(segment POI, segment edge)
{
LL p = det(POI.A, POI.B, edge.A);
LL q = det(POI.A, POI.B, edge.B);
LL s = det(edge.A, edge.B, POI.A);
LL t = det(edge.A, edge.B, POI.B);
if(p * q < 0 &&
s * t < 0)
return true;
return false;
}
bool onEdge(punct crima, segment edge)
{
LL left, right, down, up;
left = min(edge.A.x, edge.B.x);
right = left ^ edge.A.x ^ edge.B.x;
down = min(edge.A.y, edge.B.y);
up = down ^ edge.A.y ^ edge.B.y;
if(left <= crima.x && crima.x <= right &&
down <= crima.y && crima.y <= up &&
det(crima, edge.A, edge.B) == 0)
return true;
return false;
}
int main()
{
in >> N >> M;
Edges.reserve(N+4);
LL prevA, prevB;
in >> prevA >> prevB;
LL remA = prevA, remB = prevB;
for(int i = 2; i <= N; ++i)
{
LL A, B;
in >> A >> B;
Edges.push_back(segment(punct(prevA, prevB), punct(A, B)));
prevA = A, prevB = B;
}
Edges.push_back(segment(punct(prevA, prevB), punct(remA, remB)));
int Result = 0;
while(M--)
{
LL x, y;
in >> x >> y;
punct crima = punct(x, y);
segment POI = segment(crima, punct(x+1, 666013));
int crossCount = 0;
for(auto edge : Edges)
{
if(onEdge(crima, edge))
{
crossCount = 1;
break;
}
else if(cross(POI, edge))
++crossCount;
}
if(crossCount&1)
++Result;
}
out << Result << '\n';
return 0;
}