Pagini recente » Cod sursa (job #378023) | Cod sursa (job #1093161) | Cod sursa (job #1087317) | Cod sursa (job #1615704) | Cod sursa (job #1096212)
#include <fstream>
#include <algorithm>
#include <vector>
#define NMax 810
using namespace std;
ifstream f ("poligon.in");
int nowbanda;
int n, m;
int ans;
int A[NMax], B[NMax];
long long C[NMax];
struct punct
{
int x, y;
punct(){}
punct(const int x, const int y)
{
this -> x = x;
this -> y = y;
}
};
punct P[NMax];
int banda[NMax], nbanda, auxbanda[NMax], nauxbanda;
vector <int> v[NMax];
bool visited[NMax];
void Read()
{
f>>n>>m;
for (int i = 1; i<=n ;++i)
{
f>>P[i].x>>P[i].y;
auxbanda[++nauxbanda] = P[i].x;
}
P[n+1] = P[1];
}
inline bool cmp(const int &ind1, const int &ind2)
{
double mij = 1.0 * (banda[nowbanda] + banda[nowbanda+1]) / 2;
int ymij1 = (- 1.0*C[ind1] - A[ind1] * mij) / B[ind1];
int ymij2 = (- 1.0*C[ind2] - A[ind2] * mij) / B[ind2];
return ymij1 < ymij2;
}
inline int GetBanda(const int x)
{
int st = 1, dr = nbanda - 1, mij;
while (st <= dr)
{
mij = (st+dr) >> 1;
if (banda[mij] <= x && x < banda[mij+1])
return mij;
if (banda[mij] <= x)
st = mij+1;
else
dr = mij-1;
}
return nbanda;
}
inline int InPoligon(const int x, const int y)
{
if (x < banda[1] || x > banda[nbanda])
return 0;
int now = GetBanda(x);
if (now == nbanda)
{
if (visited[y])
return 1;
return 0;
}
int st = 0, dr = v[now].size() - 1, mij;
while (st <= dr)
{
mij = (st+dr)>>1;
int ind = v[now][mij];
long long det = 1LL*A[ind] * x + 1LL*B[ind]*y + C[ind];
if (det == 0)
return 1;
if (det > 0LL) // e deasupra
st = mij+1;
else
dr = mij-1;
}
if (st == v[now].size())
return 0;
if (dr == -1)
return 0;
if ((st & 1) == 1)
return 1;
return 0;
}
void Solve()
{
sort(auxbanda + 1, auxbanda + nauxbanda + 1);
banda[++nbanda] = auxbanda[1];
for (int i = 2; i<=nauxbanda; ++i)
if (auxbanda[i] != banda[nbanda])
banda[++nbanda] = auxbanda[i];
for (int 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;
}
for (int i = 1; i < nbanda; ++i)
{
for (int j = 1; j <= n; ++j)
if (min(P[j].x, P[j+1].x) <= banda[i] && banda[i] < max(P[j].x, P[j+1].x))
v[i].push_back(j);
nowbanda = i;
sort(v[i].begin(), v[i].end(), cmp);
}
for (int j = 1; j<=n; ++j)
if (max(P[j].x, P[j+1].x) == banda[nbanda])
{
if (min(P[j].x, P[j+1].x) == banda[nbanda])
{
int inflim = min(P[j].y, P[j+1].y), suplim = max(P[j].y, P[j+1].y);
for (int i = inflim; i <= suplim; ++i)
visited[i] = true;
}
else if (P[j].x == banda[nbanda])
visited[P[j].y] = true;
else
visited[P[j+1].y] = true;
}
while (m--)
{
int x, y; f>>x>>y;
ans += InPoligon(x, y);
}
ofstream g("poligon.out");
g<<ans<<"\n";
g.close();
}
int main()
{
Read();
Solve();
return 0;
}