Cod sursa(job #1944650)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 29 martie 2017 10:41:08
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define ll long double
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
pair<ll,ll> v[120001];
pair<ll,ll> st[120001];
bool det(pair<ll,ll> x, pair<ll,ll> y,pair<ll,ll> z)
{
    ll s1,s2;
    s1=x.first*y.second+y.first*z.second+z.first*x.second;
    s2=x.second*y.first+y.second*z.first+x.first*z.second;
    return s1>=s2;
}
bool cmp(pair<ll,ll> x, pair<ll,ll> y)
{
    return (x.first-v[1].first)*(y.second-v[1].second)<(x.second-v[1].second)*(y.first-v[1].first);
}
int main()
{int n;
f>>n;
int i,poz;
ll minn=1000000001;
for(i=1;i<=n;i++)
{
    f>>v[i].first>>v[i].second;
    if(v[i].first<minn) {minn=v[i].first; poz=i;}
}
swap(v[1],v[poz]);
sort(v+2,v+n+1,cmp);
int k=2;
st[1]=v[1];
st[2]=v[2];
for(i=3;i<=n;i++)
{
    while(k>1 and det(st[k-1],st[k],v[i]))
    k--;
    st[++k]=v[i];
}
g<<k<<'\n';
for(i=k;i>=1;i--)
    g<<fixed<<setprecision(6)<<st[i].first<<' '<<st[i].second<<'\n';
    return 0;
}