Pagini recente » Cod sursa (job #1061317) | Cod sursa (job #963520) | Cod sursa (job #813529) | Cod sursa (job #2892941) | Cod sursa (job #1992749)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
const int INF = 1000001;
struct punct
{
double x, y;
};
struct dreapta
{
double a, b, c;
};
struct segm
{
punct A, B;
};
struct lat_banda
{
int nrlat;
segm v[802];
};
punct vf[802];
lat_banda b[802];
double banda[802];
int N, K;
void citirevf()
{
f >> N >> K;
for(int i = 1; i <= N; i++)
{
f >> vf[i].x >> vf[i].y;
banda[i] = vf[i].x;
}
vf[N + 1] = vf[1];
}
void pastdis(double v[], int &lg)
{
int nr = 1;
for(int i = 2; i <= lg; i++)
if(v[i] > v[i - 1])
v[++nr] = v[i];
lg = nr;
}
inline dreapta ecuatie(punct A, punct B)
{
dreapta d;
d.a = A.y - B.y;
d.b = B.x - A.x;
d.c = A.x * B.y - B.x * A.y;
return d;
}
int comp(double x, double y)
{
return x < y;
}
int comp2(segm AB, segm CD)
{
return AB.A.y + AB.B.y < CD.A.y + CD.B.y;
}
long long det(const punct &A, const punct &B, const punct &C)
{
// > 0 => spre stanga
return (long long)(A.x - B.x) * (B.y - C.y) - (long long)(A.y - B.y) * (B.x - C.x);
}
int cautbin_pct(punct P, lat_banda b)
{
int st = 1, dr = b.nrlat, mij, nr=0;
while(st <= dr)
{
mij = (st + dr) / 2;
long long dd = det(b.v[mij].A, b.v[mij].B, P);
if(dd > 0)
{
st = mij + 1;
nr = mij;
}
else
if(dd < 0)
dr = mij - 1;
else //dd == 0
return 1;
}
return nr%2;
}
int cautbin(double x, int &ind)
{
int st = 1, dr = N, mij;
if(x < banda[1] || x > banda[N])
return 0;
while(st <= dr)
{
mij = (st + dr) / 2;
if(x > banda[mij])
{
if(x < banda[mij + 1])
{
ind = mij;
return 1;
}
st = mij + 1;
}
else
if(x < banda[mij])
dr = mij - 1;
else //x==banda[mij]
{
ind = mij;
return -1;
}
}
}
int main()
{
citirevf();
sort(banda + 1, banda + N + 1, comp);
int lgb = N, nrint = 0;
pastdis(banda, lgb);
banda[lgb + 1] = INF;
// for(int i = 1; i <= lgb; i++)
// cout << banda[i] << ' ';
//cout << endl;
for(int q = 1; q <= lgb; q++)
{
for(int i = 1; i <= N; i++)
{
int j = i + 1;
int imaxx, iminx;
if(vf[i].x > vf[j].x)
{
imaxx = i;
iminx = j;
}
else
{
imaxx = j;
iminx = i;
}
if(vf[iminx].x <= banda[q] && banda[q + 1] <= vf[imaxx].x)
{
dreapta d;
d = ecuatie(vf[i], vf[j]);
if(d.b != 0)
{
segm AB;
AB.A.x = banda[q];
AB.B.x = banda[q + 1];
AB.A.y = (-d.a * banda[q] - d.c) / d.b;
AB.B.y = (-d.a * banda[q + 1] - d.c) / d.b;
b[q].v[++b[q].nrlat] = AB;
}
}
}
sort(b[q].v + 1, b[q].v + 1 + b[q].nrlat, comp2);
}
for(int q = 1; q <= K; q++)
{
int ind;
punct p;
f >> p.x >> p.y;
//cout<<"x="<<p.x<<endl;
int rez = cautbin(p.x, ind);
int nrlp;
b[0].nrlat=0;
switch(rez)
{
case 1:
if(cautbin_pct(p,b[ind]))
nrint++;
break;
case -1:
if(cautbin_pct(p,b[ind]) || cautbin_pct(p,b[ind-1]))
nrint++;
}
}
g << nrint;
return 0;
}