Cod sursa(job #1564424)

Utilizator andreiulianAndrei andreiulian Data 9 ianuarie 2016 17:51:21
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,s[120005],u,s2[120005],u2;
struct punct{
    long double x,y;
}p[120005];
bool cmp(punct a, punct b){
    if(a.y<b.y) return 1;
    if(a.y==b.y && a.x<b.x) return 1;
    return 0;
}
int main(){
    ifstream in("infasuratoare.in");
    //ofstream out("infasuratoare.out");
    FILE *out = fopen("infasuratoare.out","w");
    in>>n;
    int i;
    for(i=1;i<=n;++i){
        in>>p[i].x>>p[i].y;
    }
    sort(p+1,p+n+1,cmp);
    s[1]=1;
    u=1;
    while(s[u]!=n){
        s[u+1]=s[u]+1;
        u++;
        while(s[u-2]!=0 &&
        ( p[s[u]].x*(p[s[u-1]].y-p[s[u-2]].y) +  p[s[u-1]].x*(p[s[u-2]].y-p[s[u]].y) + p[s[u-2]].x*(p[s[u]].y-p[s[u-1]].y) )>0  ){
            s[u-1]=s[u];
            --u;
        }
    }
    s2[1]=1;
    u2=1;
    while(s2[u2]!=n){
        s2[u2+1]=s2[u2]+1;
        u2++;
        while(s2[u2-2]!=0 &&
        ( p[s2[u2]].x*(p[s2[u2-1]].y-p[s2[u2-2]].y) +  p[s2[u2-1]].x*(p[s2[u2-2]].y-p[s2[u2]].y) + p[s2[u2-2]].x*(p[s2[u2]].y-p[s2[u2-1]].y) )<0  ){
            s2[u2-1]=s2[u2];
            --u2;
        }
    }
    //out<<u+u2-2<<'\n';
    fprintf(out,"%d\n",u+u2-2);
    for(i=1;i<=u;++i) fprintf(out,"%.8llf %.8llf\n",p[s[i]].x,p[s[i]].y);//out<<p[s[i]].x<<' '<<p[s[i]].y<<'\n';
    for(i=u2-1;i>1;--i) fprintf(out,"%.8llf %.8llf\n",p[s[i]].x,p[s[i]].y);//out<<p[s2[i]].x<<' '<<p[s2[i]].y<<'\n';
    in.close();
    fclose(out);
    return 0;
}