Pagini recente » Cod sursa (job #1046415) | Cod sursa (job #1412289) | Cod sursa (job #2782963) | Cod sursa (job #2537123) | Cod sursa (job #1169176)
#include<fstream>
#include<algorithm>
#include<vector>
#define N 810
#define eps 0.000000001
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
int n,m,i,j,sol,poz,mini,maxi,banda,nrb,x,y,band[N],viz[60100];
struct punct{
int x,y;
}p[N];
struct ecuatie{int a,b,c;
double n,m;
}ec[N];
vector<int>a[N];
inline bool cmp(int a,int b){
double mij = (band[i] + band[i+1])/2.0;
double y1 = mij * ec[a].m + ec[a].n;
double y2 = mij * ec[b].m + ec[b].n;
return y2>y1+eps;
}
inline int caut_binar(int x){
int li,ls,mij;
li=1;
ls=nrb-1;
while(li <= ls)
{
mij=(li+ls)>>1;
if(band[mij] <= x && x < band[mij+1])
return mij;
if(band[mij] <= x)
{
li=mij+1;
}
else
{
li=mij-1;
}
}
return nrb;
}
inline punct pmin(punct a,punct b){
if(a.x < b.x)
return a;
return b;
}
inline punct pmax(punct a,punct b){
if(a.x > b.x)
return a;
return b;
}
inline bool mai_sus(punct O,punct A, punct B){
int x=(A.x-O.x)*(B.y-O.y)-(A.y-O.y)*(B.x-O.x);
return (x>=0)?1:0;
}
inline int caut_binar_poz(int x,int y){
int li,ls,mij,sol;
long long det;
sol=0;
li=0;
ls=a[banda].size()-1;
while(li <= ls){
mij=(li+ls)>>1;
det=ec[mij].a * x + ec[mij].b * y + ec[mij].c;
if(det == 0)
return 1;
if(det > 0LL)
li=mij+1;
else
ls=mij-1;
}
if(li == a[banda].size())
return 0;
if(ls == -1)
return 0;
if(li & 1)
return 1;
return 0;
}
int main()
{
f>>n>>m;
for(i = 1 ; i <= n ; ++ i)
{
f>>p[i].x>>p[i].y;
band[i]=p[i].x;
}
p[n+1]=p[1];
for( i = 1 ; i <= n ;++ i)///Calculez ecuatiile dreptelor
{
punct a,b;
a=p[i];
b=p[i+1];
if(a.x > b.x)
swap(a,b);
ec[i].a= a.y - b.y;
ec[i].b= b.x - a.x;
ec[i].c= a.x * b.y - a.y * b.x;
ec[i].m= -1.0 * ec[i].a / ec[i].b;
ec[i].n= -1.0 * ec[i].c / ec[i].b;
}
sort(band+1,band+n+1);///Fac benzile
nrb=1;
band[nrb]=band[1];
for(i = 2 ; i <= n ; ++ i)
if(band[i]!=band[nrb])
band[++nrb]=band[i];
for(i = 1 ; i <= nrb ; ++ i)/// Ducem dreapta paralela cu OY prin band[i]
{
for(j = 1 ; j <= n ; ++ j)
if(min(p[j].x, p[j+1].x) <= band[i] && band[i] < max(p[j].x, p[j+1].x))
/// Daca intersecteaza segmentul j
{
a[i].push_back(j);
}
sort(a[i].begin(),a[i].end(),cmp);
}
return 0;
for(i = 1 ; i <= n ; ++ i)
{
if(max(p[i].x, p[i+1].x) == band[nrb])
{
if(p[i].x == p[i+1].x)
{
mini=min(p[i].y, p[i+1].y);
maxi=max(p[i].y, p[i+1].y);
for(j = mini ; j <= maxi ; ++ j)
viz[j]=1;
}
else
if(p[i].x == band[nrb])
viz[p[i].y]=1;
else
viz[p[i+1].y]=1;
}
}
for( i = 1 ; i <= m ; ++ i)
{
f>>x>>y;
if(band[1] > x || band[nrb] < x)
continue;
banda=caut_binar(x);///In ce banda se afla
if(banda == nrb)
{
if(viz[y])
++sol;
continue;
}
sol+=caut_binar_poz(x,y);
}
g<<sol<<'\n';
return 0;
}