Pagini recente » Cod sursa (job #1747148) | Cod sursa (job #1449005) | Cod sursa (job #3293257) | Cod sursa (job #657498) | Cod sursa (job #1685685)
//18:45
# include <bits/stdc++.h>
# define NR 1005
# define INF 999999999
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
vector <int> v[NR];
struct elem {
int x, y;
}p[NR];
bool cmp (int x, int y) {
double midx=((double)(p[x].x + p[x+1].x)/2),
midy=((double)(p[y].x + p[y+1].x)/2);
return midx < midy;
}
int i,j,n,m,x,y,online,sol,ci,cs,mij,poz,POZ,Q,nrX,VV;
int A[NR], B[NR], C[NR], X[NR];
double panta[NR];
bool sus (int x, int y, int D) {
if (A[D]*x + B[D]*y + C[D]==0) online=1;
elem E;
if (p[D].x < p[D+1].x) E=p[D];
else E=p[D+1];
double P1=((double)(y - E.y))/(x - E.x);
if (P1 > panta[D]) return 1;
else return 0;
}
int main ()
{
f>>n>>Q;
for (int i=1; i<=n; ++i) {
f>>p[i].x>>p[i].y;
X[++nrX]=p[i].x;
}
p[n+1]=p[1];
//detalii segmente
for (i=1; i<=n; ++i) {
A[i]=p[i].y - p[i+1].y;
B[i]=p[i+1].x - p[i].x;
C[i]=1LL*p[i].x * p[i+1].y - 1LL*p[i+1].x * p[i].y;
if (B[i]==0) {
if (A[i]<0) panta[i]=INF;
else panta[i]=-INF;
}
else panta[i]=(double)(-A[i])/B[i];
}
//drepte
VV=1; sort (X+1, X+nrX+1);
for (int i=2; i<=nrX; ++i)
if (X[i]!=X[VV]) X[++VV]=X[i];
for (int i=1; i<=VV; ++i) {//fiecare dreapta
for (int j=1; j<=n; ++j) {
if (min(p[j].x, p[j+1].x)<=X[i] && X[i]<=max(p[j].x, p[j+1].x)) {
v[i].push_back(j);
}
}
sort (v[i].begin(), v[i].end(), cmp);
}
for (int i=1; i<=Q; ++i) {
f>>x>>y;
//caut binar fasia
if (x<X[1] || X[VV]<x) continue;
ci=1; cs=VV; poz=0;
while (ci<=cs) {
mij=(ci+cs)/2;
if (X[mij]<=x) ci=mij+1, poz=mij;
else cs=mij-1;
}
// caut binar cate segmente sunt mai jos decat el
online=0; ci=0; cs=v[poz].size()-1; POZ=-1;
while (ci<=cs) {
mij=(ci+cs)/2;
if (sus(x, y, v[poz][mij])) ci=mij+1, POZ=mij;
else cs=mij-1;
}
if ((POZ+1)%2==1 || online) ++sol;
}
g<<sol<<"\n";
return 0;
}