Cod sursa(job #1414424)

Utilizator rangerChihai Mihai ranger Data 2 aprilie 2015 16:41:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

const int nmax=120010;
const long long inf=100000000000;
int n;
struct point
{
    double x,y,panta;
};
bool cmp(point i,point j) {return (i.panta<j.panta); }
point p[nmax];
vector<point> st;

double cp(point i,point j,point k)
{
    return i.x*j.y+j.x*k.y+k.x*i.y-i.y*j.x-j.y*k.x-k.y*i.x;
}

int main()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
    point first=p[1];int poz=1;
    for (int i=2;i<=n;i++)
        if (p[i].x<first.x || (p[i].x==first.x && p[i].y<first.y))
            first=p[i],poz=i;
    swap(p[1],p[poz]);
    for (int i=2;i<=n;i++) p[i].panta=(p[i].x==p[1].x)?inf:(p[i].y-p[1].y)/(p[i].x-p[1].x);
    sort(p+2,p+n+1,cmp);
    st.push_back(p[1]);
    st.push_back(p[2]);
    for (int i=3;i<=n;i++) {
        while (!st.empty() && cp(st[st.size()-1],st[st.size()-2],p[i])>=0)
            st.pop_back();
        st.push_back(p[i]);
    }
    cout<<st.size()<<"\n";
    for (int i=0;i<st.size();i++) cout<<setprecision(12)<<fixed<<st[i].x<<" "<<st[i].y<<"\n";
    return 0;
}