Pagini recente » Cod sursa (job #2889755) | Cod sursa (job #2889792) | Clasament info_de_performanta | Cod sursa (job #1491498) | Cod sursa (job #658362)
Cod sursa(job #658362)
#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 ()
{
for (int i=1; i<X[0]; ++i)
{
for (int j=1; j<=NLines; ++j)
{
if (X[i]<=Lines[j].A.x and Lines[j].B.x<=X[i+1])
{
Lines[j].Mid=GetY (Lines[j], (X[i]+X[i+1])/2);
Strips[i].push_back (Lines[j]);
}
}
sort (Strips[i].begin (), Strips[i].end (), Compare);
}
}
inline int SearchStrip (int x)
{
int L=1, R=X[0]-1, Strip=0;
while (L<=R)
{
int Mid=L+(R-L)/2;
if (x<=X[Mid+1])
{
Strip=Mid;
L=Mid+1;
}
else
{
R=Mid-1;
}
}
return Strip;
}
inline int Sign (pii A, pii B, pii C)
{
return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-A.y*B.x-A.x*C.y;
}
inline int SearchLine (int SI, pii Point)
{
int L=0, R=Strips[SI].size ()-1, Line=0;
while (L<=R)
{
int Mid=L+(R-L)/2;
if (Sign (Strips[SI][Mid].A, Strips[SI][Mid].B, Point)>=0)
{
Line=Mid;
L=Mid+1;
}
else
{
R=Mid-1;
}
}
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+1)%2==1 or Sign (Strips[Strip][Line].A, Strips[Strip][Line].B, Point)==0)
{
++S;
}
}
printf ("%d\n", S);
return 0;
}