Cod sursa(job #1117854)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 23 februarie 2014 20:39:53
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <queue>
#include <string>
#include <map>
#include <set>


#define DN 120005
#define pb push_back
#define mp make_pair
#define per pair<double,double>
#define INF (1<<30)
#define LL long long
#define un unsigned
#define x first
#define y second
using namespace std;


per p[DN],st[DN];
int sz;

/*
bool cmp(per a,per b){

    return atan2(a.y-p[1].y,a.x-p[1].x) < atan2(b.y-p[1].y,b.x-p[1].x);
}*/
double ccw( per a, per b, per c){

    return ( b.x - a.x ) * ( c.y - a.y ) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(per a,per b){
    return ccw(p[1],a,b) < 0;
}

int main()
{
    int n;
    ifstream f("infasuratoare.in");
    f>>n;
    f>>p[1].x>>p[1].y;
    for(int i=2;i<=n;++i){
        f>>p[i].x>>p[i].y;

        if(p[1].x == p[i].x && p[1].y > p[i].y)
            swap(p[i],p[1]);
        if(p[1].x > p[i].x)
            swap(p[1],p[i]);
    }
    sort(p+2,p+n+1,cmp);
    st[ ++sz ] = (p[1]);
    st[ ++sz ] = (p[2]);

    for(int i=3;i<=n;++i){

        for(  ; sz>=2 && ccw(st[ sz -1 ],st[sz],p[i]) > 0 ; )
            --sz;
        st[++sz] = p[i];
    }
    cout<<sz<<"\n";
    for(int i=1;i<=sz;++i)
        cout<<fixed<< setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";

    return 0;
}