Cod sursa(job #1238932)

Utilizator nicnic28nichita trita nicnic28 Data 7 octombrie 2014 22:32:44
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

const int N=1+1e5;
double abs(double a){
    return a>-a?a:-a;
}

struct Pct{
    double x,y;
} p[N],s[5001];
int t,n;

bool better(Pct a, Pct b){
    double f=(b.x-p[1].x)*(a.y-p[1].y),g=(a.x-p[1].x)*(b.y-p[1].y);
    if(g-f>0) return true;
    if(g-f==0 && (abs(a.x-p[0].x)<abs(b.x-p[0].x) || abs(a.y-p[0].y)<abs(b.y-p[0].y))) return true;
    return false;
}
void emsort(int st, int dr){
    if(st>=dr) return ;
    Pct a;
    int i,j;
    for(i=j=st ; j<dr  ; j++){
        if(better(p[j],p[dr])){
            a=p[j];
            p[j]=p[i];
            p[i]=a;
            i++;
        }
    }
    a=p[i];
    p[i]=p[dr];
    p[dr]=a;
    emsort(st,i-1);
    emsort(i+1,dr);
}

bool bad(Pct a){
    return (s[t].x-a.x)*(s[t-1].y-a.y)>=(s[t].y-a.y)*(s[t-1].x-a.x);
}
int main()
{
    int z;
    in>>n;
    in>>p[1].x>>p[1].y;
    z=1;
    for(int i=2 ; i<=n ; i++){
        in>>p[i].x>>p[i].y;
        if(p[i].y<p[z].y) z=i;
        if(p[i].y==p[z].y && p[i].x<p[z].x) z=i;
    }
    s[++t]=p[z];
    Pct a=p[z];
    p[z]=p[1];
    p[1]=a;
    emsort(2,n);
    s[++t]=p[2];
    s[++t]=p[3];
    for(int i=4 ; i<=n ; i++){
        while(bad(p[i]) && t>2){
            t--;
        }
        s[++t]=p[i];
    }
    out<<t<<'\n';
    for(int i=1 ; i<=t ; i++){
        out<<s[i].x<<' '<<s[i].y<<'\n';
    }
    return 0;
}