Cod sursa(job #1929218)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 17 martie 2017 12:17:01
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
const int nmax=120023;
pair<double,double>v[nmax];
double coord1=1000000003,coord2=1000000003;
int ind;
int n;
int stck[nmax];
int comp(const pair<double,double> &a,const pair<double,double> &b)
{
    return (a.second-coord2)*(b.first-coord1)<(b.second-coord2)*(a.first-coord1);
}
double arie(double x1,double y1,double x2,double y2,double x3,double y3)
{
    return (double)(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));
}
int main()
{
    freopen ("infasuratoare.in","r",stdin);
    freopen ("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&v[i].first,&v[i].second);
        if(coord1>v[i].first)
        {
            coord1=v[i].first;
            coord2=v[i].second;
            ind=i;
        }
        else if(coord1==v[i].first&&coord2>v[i].second)
        {
            coord2=v[i].second;
            ind=i;
        }
    }
    swap(v[1],v[ind]);
    sort(v+2,v+n+1,comp);
    stck[1]=1,stck[2]=2;
    int ps=2;
    for(int i=3;i<=n;i++)
    {
        while(arie(v[stck[ps-1]].first,v[stck[ps-1]].second,v[stck[ps]].first,v[stck[ps]].second,v[i].first,v[i].second)<0&&ps>=2) --ps;
        stck[++ps]=i;
    }
    printf("%d\n",ps);
    for(int i=1;i<=ps;i++) printf("%lf %lf\n",v[stck[i]].first,v[stck[i]].second);
}