Mai intai trebuie sa te autentifici.
Cod sursa(job #2059068)
Utilizator | Data | 6 noiembrie 2017 17:09:41 | |
---|---|---|---|
Problema | Poligon | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Lista lui wefgef | Marime | 1.41 kb |
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
FILE *f=fopen("poligon.in","r");
FILE *g=fopen("poligon.out","w");
vector<int> V[60005];
struct punct{
int x,y;
punct()
{
x=y=0;
}
punct(int a,int b)
{
x=a;
y=b;
}
};
struct dreapta
{
int a,b;
long long c;
dreapta()
{
;
}
dreapta(punct A,punct B)
{
a=B.y-A.y;
b=A.x-B.x;
c=1LL*B.x*A.y-1LL*A.x*B.y;
}
};
punct P[60005];
dreapta V[60005];
int N,M;
int x[60005];
int nx;
vector<dreapta> strip[60005];
set<punct> segm[60005];
int main()
{
fscanf(f,"%d %d",&N,&M);
for(int i=1;i<=N;i++)
{
fscanf(f,"%d%d",&P[i].x,&P[i].y);
x[i]=P[i].x;
}
sort(x+1,x+1+N);
x[0]=-1;
for(int i=1;i<=N;i++)
{
if(x[nx]!=x[i])
x[++nx]=x[i];
V[i]=dreapta(P[i],P[i%N+1]);
}
for(int i=1;i<=nx;i++)
{
stx[i]=0;drx[i]=-1;
for(int j=1;j<=N;j++)
{
if(V[j].b==0)
{
if(P[j].x==x[i]) {segm[i].insert(P[j].y);segm[i].insert(P[j%N+1].y);}
continue;
}
if(det(P[j],{x[i],0},{x[i],1})*det(P[j%N+1],{x[i],0},{x[i],1}))
strip[i].push_back(V[j]);
}
}
fclose(f);
fclose(g);
return 0;
}