Pagini recente » Cod sursa (job #1369854) | Cod sursa (job #1160760) | Cod sursa (job #1156353) | Cod sursa (job #1369450) | Cod sursa (job #1199672)
#include<fstream>
#include<algorithm>
#include<vector>
#define N 810
#define eps 1e-9
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;
long long 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 = 0;
ls = nrb + 1;
while(li + 2 <= ls)
{
mij = (li + ls) >> 1;
if(band[mij] <= x)
{
li = mij;
}
else
{
ls = mij;
}
}
return li;
}
inline int caut_binar_poz(int x,int y){
int li , ls , mij;
long long det;
sol = 0;
li = -1;
ls = a[banda].size();
while(li + 2 <= ls){
mij = (li + ls) >> 1;
int poz = a[banda][mij];
det = 1LL * ec[poz].a * x + 1LL * ec[poz].b * y + ec[poz].c;
if(det == 0)
return 1;
if(det > 0LL)///Deasupra
li = mij;
else///Dedesupt
ls = mij - 1;
}
++ li;
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 = 1LL * a.x * b.y - 1LL * 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;
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);
}
for(i = 1 ; i <= n ; ++ i)
{
if(max(p[i].x , p[i + 1].x) == band[nrb])
{
if(min(p[i].x , p[i + 1].x) == band[nrb])
{
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( x < band[1] || 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;
}