Cod sursa(job #1126088)

Utilizator sebinechitasebi nechita sebinechita Data 26 februarie 2014 21:14:21
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iomanip>
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define MAX 121000

pair<double, double> a[MAX];

int stiva[MAX], dr, stiva1[MAX], dr1;

inline bool cmp(pair<double, double> a, pair<double, double> b)
{
    if(a.first==b.first)
        return a.second>b.second;
    return a.first<b.first;
}

bool dreapta(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
    double x=b.first-a.first;
    double y=b.second-a.second;
    double x1=c.first-a.first;
    double y1=c.second-a.second;
    if(x==0)
        return 0;
    if(x1==0)
        return 1;
    return (double)y/x>(double)y1/x1;
}

int main()
{
    int n, i;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a[i].first>>a[i].second;
    }
    sort(a+1, a+n+1, cmp);
    for(i=1;i<=n;i++)
    {
        while(dr>1 && dreapta(a[stiva[dr]], a[stiva[dr-1]], a[i]))
            dr--;
        stiva[++dr]=i;
    }
    for(i=1;i<=n;i++)
    {
        while(dr1>1 && !dreapta(a[stiva1[dr1]], a[stiva1[dr1-1]], a[i]))
        {
            dr1--;
        }
        stiva1[++dr1]=i;
    }
    fout<<dr1+dr-2<<"\n";
    for(i=dr1-1;i>=1;i--)
    {
        fout<<fixed<<setprecision(6)<<a[stiva1[i]].first<<" "<<a[stiva1[i]].second<<"\n";
    }
    for(i=2;i<=dr;i++)
    {
        fout<<fixed<<setprecision(6)<<a[stiva[i]].first<<" "<<a[stiva[i]].second<<"\n";
    }
}