Pagini recente » Cod sursa (job #815906) | Cod sursa (job #1386070) | Cod sursa (job #2859348) | Cod sursa (job #2772969) | Cod sursa (job #2892368)
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#define Nmax 805
#define Mmax 60002
#define eps 0.00000001
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
int n,m,nrL,x,y,nr,X;
struct point{
int x,y;
}P[Nmax];
struct line{
point A,B;
line(point _A,point _B){
A = _A;
B = _B;
if (A.x>B.x) swap(A,B);
}
line(){}
bool operator == (const line &oth) const{
return A.x==oth.A.x && A.y == oth.A.y && B.x == oth.B.x && B.y == oth.B.y;
}
}L[Nmax];
struct event{
line L;
bool add;
};
vector<int> M[Mmax];
vector<event> E[Mmax];
vector<line> S;
void dell(line L){
for(int i=0;i<S.size();i++)
if (S[i]==L){
for (;i+1<S.size();i++) S[i] = S[i+1];
S.pop_back();
return;
}
}
double getY(line L, int x){
return (double)(x - L.A.x) * (L.B.y - L.A.y) / (L.B.x - L.A.x) + L.A.y;
}
int UPline(int x,int y){
int p = 1, st = 0;
if (S.empty()) return 0;
for (;p<S.size();p<<=1);
for (;p>=1;p>>=1){
if (st+p<S.size() && abs(getY(S[st+p],x) - y)<=eps) return 1;
if (st+p<S.size() && getY(S[st+p],x) > y) st+=p;
}
if (abs(getY(S[st],x) - y)<=eps) return 1;
if (getY(S[st],x) > y) st++;
return st;
}
bool comp(line L1,line L2){
if (abs(getY(L1,X) - getY(L2,X)) < eps)
return (L1.B.y > L2.B.y || L1.A.y > L2.A.y);
return getY(L1,X) > getY(L2,X);
}
int main()
{
f>>n>>m;
for (int i=1;i<=n;i++) f>>P[i].x>>P[i].y;
for (int i=1;i<=m;i++) f>>x>>y,M[x].push_back(y);
P[n+1] = P[1];
for (int i=1;i<=n;i++)
if (P[i].x!=P[i+1].x) L[++nrL] = *new line(P[i],P[i+1]);
else
for (int j=0;j<M[P[i].x].size();j++)
if (min(P[i].y,P[i+1].y)<=M[P[i].x][j] && max(P[i].y,P[i+1].y)>=M[P[i].x][j])
nr++,M[P[i].x][j] = -1;
for (int i=1;i<=nrL;i++){
E[L[i].A.x].push_back({L[i],true});
E[L[i].B.x].push_back({L[i],false});
}
for (int i=0;i<=60000;i++){
for (int j=0;j<E[i].size();j++)
if (E[i][j].add) S.push_back(E[i][j].L);
else dell(E[i][j].L);
if (!E[i].empty() || (i>0 && !E[i-1].empty())) X = i,sort(S.begin(),S.end(),comp);
for (int j=0;j<M[i].size();j++) if (M[i][j]!=-1 && UPline(i,M[i][j])%2) nr++;
}
g<<nr;
return 0;
}