Pagini recente » Cod sursa (job #471715) | Cod sursa (job #2388181) | Cod sursa (job #387804) | Cod sursa (job #519671) | Cod sursa (job #617650)
Cod sursa(job #617650)
#include<cstdio>
#include<vector>
#include<algorithm>
#include<fstream>
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;
ifstream fin("infasuratoare.in");
fin>>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++)
{
fin>>X[i]>>Y[i];
if(X[i]<X[P0] || (X[i]==X[P0] && Y[i]<Y[P0]))
P0=i;
}
fin.close();
//selectez toate punctele in afara de P0 pentru a le sorta
for(i=1;i<P0;i++)
A[i]=i;
for(i=P0+1;i<=n;i++)
A[i-1]=i;
m=n-1;
//le sortez
sort(A+1,A+m+1,Sortare);
//bag punctele in stiva
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=nr;i>=0;i--)
printf("%lf %lf\n",X[St[i]],Y[St[i]]);
return 0;
}