Pagini recente » Cod sursa (job #740506) | Cod sursa (job #31762) | Cod sursa (job #2698379) | Cod sursa (job #2869687) | Cod sursa (job #391077)
Cod sursa(job #391077)
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define M1 120000
using namespace std;
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
double x[M1],y[M1];
int pi,n,i,a[M1],st[M1];
void citire(){
fscanf(f,"%d",&n);
pi=1;
for(i=1;i<=n;i++){
fscanf(f,"%lf %lf",&x[i],&y[i]);
if(x[i]<x[pi] || (x[i]==x[pi] && y[i] <y[pi])){
pi=i;
}
}
}
/*
long double d1,d2;
d1= (long double)(y[i]-y[pi])*(x[j]-x[pi]);
d2= (long double)(y[j]-y[pi])*(x[i]-x[pi]);
return d1>d2;
*/
int cmp(int i,int j){
return (long double)(y[i]-y[pi])*(x[j]-x[pi])>(long double)(y[j]-y[pi])*(x[i]-x[pi]);
}
long double semn(int i1,int i2,int i3){
return (long double) x[i1]*y[i2]+x[i2]*y[i3]+y[i1]*x[i3]-y[i2]*x[i3]-x[i1]*y[i3]-x[i2]*y[i1];
}
int main(){
citire();
for(i=1;i<=n;i++){
if(i==pi) continue;
a[++a[0]]=i;
}
//x[pi]+=(long double)1.1050003;
//y[pi]+=(long double)1.1050003;
sort(a+1,a+n,cmp);
st[st[0]=1]=pi;
for(i=1;i<n;i++){
while(st[0]>=2 && semn( st[st[0]-1],st[st[0]],a[i]) > 0 )
--st[0];
st[++st[0]]=a[i];
}
fprintf(g,"%d\n",st[0]);
reverse(st+1,st+st[0]+1);
for(i=1;i<=st[0];i++){
fprintf(g,"%lf %lf\n",x[st[i]],y[st[i]]);
}
fclose(f);
fclose(g);
return 0;
}