Pagini recente » Cod sursa (job #1942448) | Cod sursa (job #240650) | Cod sursa (job #2283647) | Cod sursa (job #2597813) | Cod sursa (job #253438)
Cod sursa(job #253438)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAX 120000
#define INF 1000000000
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"
FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");
double X[MAX],Y[MAX];
long double V[MAX];
int IND[MAX],ST[MAX];
int PI,N;
long double semn(int,int,int);
void swap(int,int);
bool cmpf(int,int);
int main()
{
int i;
fscanf(fin,"%d\n",&N);
X[0]=INF;
Y[0]=INF;
int punct_initial=0;
for(i=1;i<=N;++i)
{
fscanf(fin,"%lf %lf",&X[i],&Y[i]);
if(X[i]<X[punct_initial] || (X[i]==X[punct_initial] && Y[i]<Y[punct_initial]))
punct_initial=i;
}
fclose(fin);
PI=punct_initial;
for(i=1;i<=N;++i)
{
if(i==punct_initial)
continue;
IND[++IND[0]]=i;
}
sort(IND+1,IND+IND[0]+1,cmpf);
ST[ST[0]=1]=punct_initial;
for(i=1;i<=IND[0];++i)
{
if(IND[i]==punct_initial)
continue;
while(ST[0]>=2 && semn(ST[ST[0]-1],ST[ST[0]],IND[i]) > 0)
--ST[0];
ST[++ST[0]]=IND[i];
}
ST[++ST[0]]=punct_initial;
fprintf(fout,"%d\n",ST[0]-1);
swap(ST[1],ST[ST[0]+1]);
for(i=ST[0]-1;i>0;i--)
fprintf(fout,"%lf %lf\n",X[ST[i]],Y[ST[i]]);
fclose(fout);
return 0;
}
long double semn(int i,int j,int k)
{
return (long double) (X[i]*Y[j]+X[j]*Y[k]+X[k]*Y[i])-(Y[i]*X[j]+Y[j]*X[k]+Y[k]*X[i]);
}
bool cmpf(int i,int j)
{
return (double)(X[i]-X[PI])*(Y[j]-Y[PI])<(double)(X[j]-X[PI])*(Y[i]-Y[PI]);
}
void swap(int i,int j)
{
int k;
k=i; i=j; j=k;
}