Cod sursa(job #1963212)

Utilizator Daria09Florea Daria Daria09 Data 12 aprilie 2017 13:03:55
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define DIM 120003
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct puncte
{
    double x,y;
}a[DIM],stiva[DIM];
int n,st;
void read()
{
    f>>n;
    for(int i=1;i<=n;i++)f>>a[i].x>>a[i].y;
    f.close();
}
inline double product(puncte a,puncte b,puncte c){return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}
inline bool cmp(puncte a1,puncte b){return product(a[1],a1,b)<0;}
void sortare()
{
    int pos=1;
    for(int i=2;i<=n;++i)if(a[pos].y>a[i].y||(a[pos].y==a[i].y&&a[pos].x>a[i].x))pos=i;
    swap(a[1],a[pos]);
    sort(a+2,a+n+1,cmp);
}
void solve()
{
    sortare();
    stiva[1]=a[1]; stiva[2]=a[2]; st=2;
    for(int i=3;i<=n;i++)
    {
        while(st>=2&&product(stiva[st-1],stiva[st],a[i])>0)--st;
        stiva[++st]=a[i];
    }
}
void write()
{
    g<<fixed;
    g<<st<<'\n';
    for(int i=st;i>=1;--i)
        g<<setprecision(9)<<stiva[i].x<<" "<<stiva[i].y<<'\n';
    g.close();
}
int main()
{
    read();
    solve();
    write();
    return 0;
}