Pagini recente » Istoria paginii runda/test193120947281 | Istoria paginii runda/preoji_1 | Istoria paginii runda/dist2/clasament | Cod sursa (job #2014417) | Cod sursa (job #616391)
Cod sursa(job #616391)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const char InFile[]="poligon.in";
const char OutFile[]="poligon.out";
const int MinX=-1;
const int MaxX=60111;
const int MaxN=1024;
const int WINDING=1;
ifstream fin(InFile);
ofstream fout(OutFile);
struct point
{
int x,y;
};
struct line
{
point A,B;
};
struct line_sort
{
line l;
double mid;
};
struct cmp_line_sort
{
inline bool operator() (const line_sort &a, const line_sort &b)
{
return a.mid<b.mid;
}
};
struct strip
{
int xmin,xmax;
vector<line> l;
};
int N,M,D[MaxN],lind;
line l[MaxN];
point p[MaxN];
vector<int> v;
vector<line_sort> s[MaxN];
inline long long det(const point &a, const point &b, const point &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 sgn(const point &a, const point &b, const point &c)
{
long long val=det(a,b,c);
if(val<0)
{
return -1;
}
else if(val>0)
{
return 1;
}
return 0;
}
inline double get_y(const line &l, const double &x)
{
double x1=l.A.x;
double x2=l.B.x;
double y1=l.A.y;
double y2=l.B.y;
return y2-(x2-x)*(y2-y1)/(x2-x1);
}
inline void build()
{
sort(v.begin(),v.end());
D[++D[0]]=v[0];
for(register unsigned int i=1;i<v.size();++i)
{
if(v[i]!=v[i-1])
{
D[++D[0]]=v[i];
}
}
D[D[0]+1]=MaxX;
for(register int i=1;i<=N;++i)
{
if(p[i].x!=p[i+1].x)
{
++lind;
l[lind].A=p[i];
l[lind].B=p[i+1];
if(l[lind].A.x>l[lind].B.x)
{
swap(l[lind].A,l[lind].B);
}
}
}
line_sort ll;
ll.l.A.x=50;
ll.l.A.y=-100;
ll.l.B.x=100;
ll.l.B.y=-100;
ll.mid=-100;
for(register int i=1;i<D[0];++i)
{
for(register int j=1;j<=lind;++j)
{
if(l[j].A.x<=D[i] && D[i+1]<=l[j].B.x)
{
line_sort tl;
tl.l=l[j];
tl.mid=get_y(l[j],(D[i]+D[i-1])*0.5);
s[i].push_back(tl);
}
}
s[i].push_back(ll);
sort(s[i].begin(),s[i].end(),cmp_line_sort());
}
}
inline int search_strip(const int &x)
{
int first=0;
int step=1<<10;
for(;step;step>>=1)
{
int index=first+step;
if(index<D[0] && D[index]<=x)
{
first=index;
}
}
return first;
}
inline int search_line(const int &strip, const point &p)
{
int first=0;
int step=1<<10;
for(;step;step>>=1)
{
int index=first+step;
if(index<s[strip].size() && sgn(s[strip][index].l.A,p,s[strip][index].l.B)<=0)
{
first=index;
}
}
return first;
}
int main()
{
fin>>N>>M;
for(register int i=1;i<=N;++i)
{
fin>>p[i].x>>p[i].y;
v.push_back(p[i].x);
}
p[N+1]=p[1];
build();
int sol=0;
for(register int i=1;i<=M;++i)
{
point pq;
fin>>pq.x>>pq.y;
if(pq.x<D[1] || D[D[0]]<pq.x)
{
continue;
}
int strip=search_strip(pq.x);
int lp=search_line(strip,pq);
if(lp%2==1 || sgn(s[strip][lp].l.A,pq,s[strip][lp].l.B)==0)
{
++sol;
}
}
fin.close();
fout<<sol;
fout.close();
return 0;
}