Pagini recente » Cod sursa (job #2665465) | Cod sursa (job #814436) | Cod sursa (job #2756815) | Cod sursa (job #960517) | Cod sursa (job #2191621)
#include <fstream>
#include <vector>
#include <cmath>
#define Nmax 805
#define Mmax 60002
#define eps 0.0000001
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
int n,m,nrL,x,y,nr;
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;
bool comp(point A,point B) {return A.x<B.x;}
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 ans = 0;
for (auto it : S) if (getY(it,x) > y) ans++;
return ans;
}
int ONline(int x,int y){
for (auto it : S) if (abs(getY(it,x) - y)<eps) return 1;
return 0;
}
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]);
for (int i=1;i<=nrL;i++){
E[L[i].A.x].push_back({L[i],true});
E[L[i].A.y].push_back({L[i],false});
}
for (int i=0;i<=60000;i++){
for (auto it : E[i]) if (it.add) S.push_back(it.L);
for (auto it : M[i]) if (UPline(i,it)%2 || ONline(i,it)) nr++;
for (auto it : E[i]) if (!it.add) dell(it.L);
}
g<<nr;
return 0;
}