Cod sursa(job #889300)

Utilizator stefanzzzStefan Popa stefanzzz Data 24 februarie 2013 13:04:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define MAXN 120005
#define INF 2000000000
#define EPS 0.000000000001
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct punct{
    double x,y,up;};

int n,mni;
double mnx=INF,mny;
punct p[MAXN],a,b,c;
vector<punct> st;

bool Comp(punct p1,punct p2){
    return p1.up<p2.up;}
double ABS(double m){
    return m>0?m:(-m);}

int main()
{
    int i;
    f>>n;
    for(i=1;i<=n;i++){
        f>>p[i].x>>p[i].y;
        if(ABS(p[i].x-mnx)<EPS&&p[i].y<mny){
            mny=p[i].y;
            mni=i;
            continue;}
        if(p[i].x<mnx){
            mnx=p[i].x;
            mny=p[i].y;
            mni=i;}}
    for(i=1;i<=n;i++){
        if(p[i].x==mnx){
            if(mni==i)
                p[i].up=-INF;
            else
                p[i].up=INF;
            continue;}
        p[i].up=(p[i].y-mny)/(p[i].x-mnx);}
    sort(p+1,p+n+1,Comp);
    st.push_back(p[1]);
    st.push_back(p[2]);
    for(i=3;i<=n;i++){
        b=st[st.size()-1];
        a=st[st.size()-2];
        c=p[i];
        while(c.x*(a.y-b.y)+c.y*(b.x-a.x)+a.x*b.y-a.y*b.x<EPS){
            b=a;
            st.pop_back();
            a=st[st.size()-2];}
        st.push_back(c);}
    g<<st.size()<<'\n'<<fixed<<setprecision(12);
    for(i=0;i<st.size();i++)
        g<<st[i].x<<' '<<st[i].y<<'\n';
    f.close();
    g.close();
    return 0;
}