Pagini recente » Cod sursa (job #1737724) | Cod sursa (job #859252) | Cod sursa (job #299083) | Cod sursa (job #2761298) | Cod sursa (job #1201912)
#include<fstream>
#include<algorithm>
#include<vector>
#define eps 0.000001
#define N 900
#define D 100000
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
int i,j,n,m,nn,poz,ppoz = D,mij,b,nrb,pe,sol,li,ls,raspuns;
double x,y,band[N];
vector<int>a[N];
struct ecuatie{int a,b,c;}ec[N];
struct punct{int x,y;}v[N];
inline bool cmp(int x,int y){
double mij = band[i] + band[i + 1];
double y1 = (-ec[x].a * mij - 2.0 * ec[x].c) / ec[x].b;
double y2 = (-ec[y].a * mij - 2.0 * ec[y].c) / ec[y].b;
return y2 - y1 > eps;
}
inline bool verif(int k){
if(x * ec[k].a + y * ec[k].b + ec[k].c == 0)
pe = 1;
double yy = (- x * ec[k].a - ec[k].c) / ec[k].b;
return y >= yy;
}
char buf[D+2];
inline int ianr(){
unsigned int nr=0;
while((buf[ppoz] < '0' || buf[ppoz] > '9') && buf[ppoz] != '-')
if(++ ppoz >= D)
fread(buf , D , 1 , stdin) , ppoz = 0;
while('0' <= buf[ppoz] && buf[ppoz] <= '9')
{
nr = nr * 10 + buf[ppoz] - '0';
if(++ ppoz >= D)
fread(buf , D , 1 , stdin) , ppoz = 0;
}
return nr;
}
int main()
{
f >> n >> m;
for(i = 1 ; i <= n ; ++ i)
{
f >> v[i].x >> v[i].y;
band[++ nrb] = v[i].x;
}
v[n + 1] = v[1];
for(i = 1 ; i <= n ; ++ i)
{
ec[i].a = v[i].y - v[i + 1].y;
ec[i].b = v[i + 1].x - v[i].x;
ec[i].c = v[i].x * v[i + 1].y - v[i + 1].x * v[i].y;
}
sort(band + 1 , band + nrb + 1);
nn = 1;
for(i = 2 ; i <= nrb ; ++ i)
if(band[i - 1] != band[i])
band[++ nn] = band[i];
nrb = nn;
for(i = 1 ; i <= nrb ; ++ i)
{
for(j = 1 ; j <= n ; ++ j)
if(min(v[j].x , v[j + 1].x) <= band[i] && max(v[j].x , v[j + 1].x) > band[i])
a[i].push_back(j);
sort(a[i].begin(),a[i].end(),cmp);
}
for(; m ; -- m)
{
f >> x >> y;
if(x < band[1] || x > band[nrb])
continue;
b = 0;
for(i = 10 ; i >= 0 ; -- i)
if(b + (1 << i) <= nrb && band[b + (1 << i )] < x)
b += (1 << i);
pe = 0;
poz = 0;
for(i = 10 ; i >= 0; -- i)
if(poz + (1 << i) <= a[b].size() && verif(a[b][poz + (1 << i) - 1]))
poz += (1 << i);
if(pe || (poz & 1))
++ raspuns;
}
g << raspuns << '\n';
return 0;
}