Pagini recente » Cod sursa (job #797921) | Cod sursa (job #2480063) | Istoria paginii runda/shimulare_shmecheri/clasament | Cod sursa (job #118306) | Cod sursa (job #658367)
Cod sursa(job #658367)
#include <cstdio>
#include <vector>
#include <algorithm>
#define Infinity 2000000000
#define NMax 805
#define x first
#define y second
#define pii pair <int, int>
using namespace std;
struct Segment
{
pii A, B;
double Mid;
};
pii P[NMax];
Segment Lines[NMax];
vector <Segment> Strips[NMax];
int N, M, X[NMax], NLines, S;
void Read ()
{
scanf ("%d %d", &N, &M);
vector <int> V;
for (int i=1; i<=N; ++i)
{
scanf ("%d %d", &P[i].x, &P[i].y);
V.push_back (P[i].x);
}
P[N+1]=P[1];
sort (V.begin (), V.end ());
X[++X[0]]=V[0];
for (unsigned i=1; i<V.size (); ++i)
{
if (V[i]!=V[i-1])
{
X[++X[0]]=V[i];
}
}
X[X[0]+1]=Infinity;
for (int i=1; i<=N; ++i)
{
if (P[i].x==P[i+1].x)
{
continue;
}
Lines[++NLines].A=P[i], Lines[NLines].B=P[i+1];
if (P[i].x>P[i+1].x)
{
swap (Lines[NLines].A, Lines[NLines].B);
}
}
}
inline bool Compare (Segment A, Segment B)
{
return A.Mid<B.Mid;
}
inline double GetY (Segment L, double x)
{
double x1=L.A.x;
double y1=L.A.y;
double x2=L.B.x;
double y2=L.B.y;
return y2-(x2-x)*(y2-y1)/(x2-x1);
}
void BuildStrips ()
{
Segment Null;
Null.A.x=50, Null.A.y=-100;
Null.B.x=100, Null.B.y=-100;
Null.Mid=-100;
for (int i=1; i<X[0]; ++i)
{
for (int j=1; j<=NLines; ++j)
{
if (Lines[j].A.x<=X[i] and X[i+1]<=Lines[j].B.x)
{
Lines[j].Mid=GetY (Lines[j], (X[i]+X[i+1])/2);
Strips[i].push_back (Lines[j]);
}
}
Strips[i].push_back (Null);
sort (Strips[i].begin (), Strips[i].end (), Compare);
}
}
inline int SearchStrip (int x)
{
int Strip=0;
for (int Step=1<<10; Step>0; Step>>=1)
{
int i=Strip+Step;
if (i<X[0] and X[i]<=x)
{
Strip=i;
}
}
return Strip;
}
inline long long Det (pii A, pii B, pii C)
{
return (long long)(B.x-A.x)*(long long)(C.y-A.y)-(long long)(B.y-A.y)*(long long)(C.x-A.x);
}
inline int Sign (pii A, pii B, pii C)
{
long long DetV=Det (A, B, C);
if (DetV<0)
{
return -1;
}
if (DetV>0)
{
return 1;
}
return 0;
}
inline int SearchLine (int SI, pii Point)
{
int Line=0;
for (int Step=1<<10; Step>0; Step>>=1)
{
int i=Line+Step;
if (i<Strips[SI].size () and Sign (Strips[SI][i].A, Point, Strips[SI][i].B)<=0)
{
Line=i;
}
}
return Line;
}
int main()
{
freopen ("poligon.in", "r", stdin);
freopen ("poligon.out", "w", stdout);
Read ();
BuildStrips ();
for (; M>0; --M)
{
pii Point;
scanf ("%d %d", &Point.x, &Point.y);
if (Point.x<X[1] or Point.x>X[X[0]])
{
continue;
}
int Strip=SearchStrip (Point.x);
int Line=SearchLine (Strip, Point);
if (Sign (Strips[Strip][Line].A, Strips[Strip][Line].B, Point)<0)
{
continue;
}
if (Line%2==1 or Sign (Strips[Strip][Line].A, Point, Strips[Strip][Line].B)==0)
{
++S;
}
}
printf ("%d\n", S);
return 0;
}