Cod sursa(job #1003660)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 1 octombrie 2013 10:47:55
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <stdio.h>
#include <limits.h>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
FILE *g=fopen("infasuratoare.out","w");
int n,S[120010];

struct puncte{
    double x,y,tg;
};
puncte v[120010],t,ct;

int cmp(puncte a,puncte b){
    return (a.tg<b.tg);
}

double det(int x,int y,int z){
    return (v[x].x*v[y].y+v[y].x*v[z].y+v[z].x*v[x].y-v[z].x*v[y].y-v[y].x*v[x].y-v[x].x*v[z].y);
}

int main(void){
    register int i,j,p=0,k;

    f>>n;
    v[0].x=INT_MAX,v[0].y=INT_MAX;
    for(i=1;i<=n;i++){
        f>>v[i].x>>v[i].y;
        if(v[i].x<v[p].x ||(v[i].x==v[p].x && v[i].y<v[p].y))
            p=i;
    }

    ct=v[p];
    v[p]=v[1],v[1]=ct;
    v[1].x=0,v[1].y=0;
    for(i=2;i<=n;i++){
        v[i].x-=ct.x;
        v[i].y-=ct.y;
        v[i].tg=(v[i].x==0?INT_MAX:(v[i].y/v[i].x));
    }

    sort(v+2,v+n+1,cmp);

    S[1]=1,S[2]=2,k=2;
    for(i=3;i<=n;i++){
        while(k>0 && det(S[k-1],S[k],i)<=0)
            k--;
        S[++k]=i;
    }

    fprintf(g,"%d\n",k);
    for(i=1;i<=k;i++){
        fprintf(g,"%.6f %.6f\n",v[S[i]].x+ct.x,v[S[i]].y+ct.y);
    }
    f.close();
    fclose(g);
    return 0;
}