Pagini recente » Cod sursa (job #2365416) | Cod sursa (job #2807162) | Cod sursa (job #38526) | Cod sursa (job #2200196) | Cod sursa (job #613581)
Cod sursa(job #613581)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,A[120010],P0;
double X[120010],Y[120010];
inline bool Sortare(int i,int j)
{
return (double)(X[i]-X[P0])*(Y[j]-Y[P0])<(double)(X[j]-X[P0])*(Y[i]-Y[P0]);
}
long double Intoarcere(int A,int B,int C)
{
return (long double)(X[A]*Y[B]+X[B]*Y[C]+X[C]*Y[A]-X[C]*Y[B]-X[B]*Y[A]-X[A]*Y[C]);
}
int main()
{
int i;
freopen("infasuratoare.in","r",stdin);
scanf("%d",&n);
//determin la citire punctul cel mai din stanga,cel mai de jos in caz de egalitate
X[0]=Y[0]=2000000000.0;
P0=0;
for(i=1;i<=n;i++)
{
scanf("%lf %lf",X+i,Y+i);
if(X[i]<X[P0] || (X[i]==X[P0] && Y[i]<Y[P0]))
P0=i;
}
//selectez toate punctele in afara de P0 pentru a le sorta
for(i=1;i<=n;i++)
{
if(i!=P0)
A[++m]=i;
}
//le sortez dupa unghiul polar
sort(A+1,A+m+1,Sortare);
//bag punctele in stiva si aplic scanarea Graham
int nr;
vector <int> St;
St.push_back(P0);
nr=0;
for(i=1;i<=m;i++)
{
while(St.size()>=2 && Intoarcere(St[nr-1],St[nr],A[i])>0)
{
//daca punctul curent face cu ultimele 2 puncte din stiva o intoarcere spre dreapta
//atunci este scos din infasuratoare punctul din varful stivei
St.pop_back();
nr--;
}
St.push_back(A[i]);
nr++;
}
//afisez punctele de pe infasuratoarea convexa
freopen("infasuratoare.out","w",stdout);
printf("%d\n",St.size());
reverse(St.begin(),St.end());
for(i=0;i<=nr;i++)
printf("%lf %lf\n",X[St[i]],Y[St[i]]);
return 0;
}