Pagini recente » Cod sursa (job #468464) | Cod sursa (job #729243)
Cod sursa(job #729243)
#include<fstream>
#include<math.h>
#include<cstdio>
#include<algorithm>
#define maxn 120010
#define inF "infasuratoare.in"
#define outF "infasuratoare.out"
using namespace std;
ifstream in(inF);
double X[maxn],Y[maxn];
int N,origine=1,v[maxn],coada[maxn];
bool cmp(int x,int y)
{
return (X[x]-X[origine])*(Y[y]-Y[origine])<(X[y]-X[origine])*(Y[x]-Y[origine]);
}
long double unghi(int x, int y, int z)
{
return (X[x]*Y[y]+X[y]*Y[z]+X[z]*Y[x])-(Y[x]*X[y]+Y[y]*X[z]+Y[z]*X[x]);
}
void read()
{
in>>N;
for(int i=1;i<=N;i++)
{
in>>X[i]>>Y[i];
if(X[i]<X[origine] || (X[i]==X[origine] && Y[i]<Y[origine])) origine=i;
}
}
int main()
{
int i;
read();
for(i=1;i<=N;i++)
{
if(i==origine) continue;
v[++v[0]]=i;
}
sort(v+1,v+v[0]+1,cmp);
coada[coada[0]=1]=origine;
for(i=1;i<=v[0];i++)
{
if(v[i]==origine) continue;
while(coada[0]>=2 && unghi(coada[coada[0]-1],coada[coada[0]],v[i])>0) --coada[0];
coada[++coada[0]]=v[i];
}
freopen("infasuratoare.out","w",stdout);
coada[++coada[0]]=origine;
printf("%d\n",coada[0]-1);
reverse(coada+1,coada+coada[0]+1);
for(i=1;i<coada[0];i++)
{
printf("%lf %lf\n",X[coada[i]],Y[coada[i]]);
}
return 0;
}