Cod sursa(job #1465157)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 26 iulie 2015 16:55:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct punct{double x,y;};
punct v[120010],stiva[120010];
int compare(int a,int b){
    if(v[a].x<v[b].x)
        return a;
    if(v[a].x>v[b].x)
        return b;
    if(v[a].y<=v[b].y)
        return a;
    return b;
}
void schimba(int a,int b){
    punct aux;
    aux=v[a];
    v[a]=v[b];
    v[b]=aux;
}
bool cmp(punct a,punct b){
    if((a.x-v[1].x)*(b.y-v[1].y)-(a.y-v[1].y)*(b.x-v[1].x)<0)
        return true;
    return false;
}
int main(){
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,i,k=2;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lf%lf",&v[i].x,&v[i].y);
    for(i=2;i<=n;i++)
        if(compare(1,i)==i)
            schimba(1,i);
    sort(v+2,v+n+1,cmp);
    stiva[1]=v[1];
    stiva[2]=v[2];
    for(i=3;i<=n;i++){
        while(k>=2&&(stiva[k].x-stiva[k-1].x)*(v[i].y-stiva[k-1].y)-(stiva[k].y-stiva[k-1].y)*(v[i].x-stiva[k-1].x)>0)
            k--;
        k++;
        stiva[k]=v[i];
    }
    printf("%d\n",k);
    for(i=k;i>=1;i--)
        printf("%.9f %.9f\n",stiva[i].x,stiva[i].y);
    return 0;
}