Pagini recente » Borderou de evaluare (job #523218) | Cod sursa (job #1192194) | Cod sursa (job #432108) | Cei mai harnici utilizatori info-arena | Cod sursa (job #251404)
Cod sursa(job #251404)
#include<cstdio>
#include<algorithm>
using namespace std;
struct Punct {
double x, y;
}a[120009];
int s[120009], ref;
int Stiva[120009],vf=-1;
int cmp(int a1, int b){
return ( (double) (a[a1].x-a[ref].x)*(a[b].y-a[ref].y))>
( (double) (a[b].x-a[ref].x)*(a[a1].y-a[ref].y));
}
void coeficienti(Punct a, Punct b, double& aa, double& bb, double& cc){
aa=a.y-b.y;
bb=b.x-a.x;
cc=b.y*a.x-b.x*a.y;
}
char semn(int gh){
double aa, bb, cc;
coeficienti(a[Stiva[vf-1]], a[Stiva[vf]], aa, bb, cc);
if(aa*a[s[gh]].x+bb*a[s[gh]].y+cc>=0)
return '+';
return '-';
}
int main(){
int i, n;
freopen("infasuratoare.in","r",stdin);
scanf("%d", &n);
for(i=0;i<n;i++){
scanf("%lf%lf",&(a[i].x), &(a[i].y));
if(a[ref].x>a[i].x||(a[ref].x==a[i].x&& a[ref].y>a[i].y))
ref=i;
}
int l=1;
for(i=0;i<n;i++)
if(i!=ref)
s[l++]=i;
sort(s+1, s+n, cmp);
s[0]=ref;
Stiva[++vf]=s[0];
Stiva[++vf]=s[1];
for(i=2;i<n;i++){
while(vf>0&&semn(i)=='-') Stiva[vf--];
Stiva[++vf]=s[i];
}
while(semn(0)=='-') --vf;
freopen("infasuratoare.out","w",stdout);
printf("%d\n",vf+1);
for(i=0;i<=vf;i++){
printf("%.6lf ",a[Stiva[i]].x);
printf("%.6lf\n",a[Stiva[i]].y);
}
return 0;
}