Cod sursa(job #1188360)

Utilizator xtreme77Patrick Sava xtreme77 Data 19 mai 2014 14:39:54
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#define PI 3.1415926535897
const int MAX = 1<<17;

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct infs{
    long double x,y;
};
infs q[MAX];
double determin(infs a,infs b,infs c){
    return 1LL*(b.x-a.x)*(c.y-a.y)-1LL*(b.y-a.y)*(c.x-a.x);
}
bool cmp(infs a,infs b){
    return determin(q[1],a,b)<0;
}
int st[MAX],itmin,n,nr;
bool cmp2(int a,int b)
{
    return atan2(q[st[a]].y,q[st[a]].x)*180/PI<atan2(q[st[b]].y,q[st[b]].x)*180/PI;
}
void solve();
int main()
{
    long double ymin=1<<29,xmin=1<<29;
    fin>>n;
    for(int i=1;i<=n;++i){
        fin>>q[i].x>>q[i].y;
        if(ymin>q[i].y){
            ymin=q[i].y;
            itmin=i;
        }
        else if(ymin==q[i].y){
            if(xmin>q[i].x)xmin=q[i].x,itmin=i;
        }
    }
    swap(q[itmin],q[1]);
    sort(q+2,q+n+1,cmp);
    solve();
    sort(st+1,st+nr+1,cmp2);
    fout<<nr<<'\n';
    for(int i=1;i<=nr;++i)fout<<fixed<<setprecision(12)<<q[st[i]].x<<' '<<q[st[i]].y<<'\n';
    return 0;
}
void solve(){
    st[++nr]=1;
    st[++nr]=2;
    st[++nr]=3;
    for(int i=4;i<=n;++i){
        while(nr>=2 and determin(q[st[nr]],q[st[nr-1]],q[i])<0)--nr;
        st[++nr]=i;
    }
}