Cod sursa(job #1917406)

Utilizator Bot32King Max Bot32 Data 9 martie 2017 12:11:19
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

#define punct pair<double,double>
#define x first
#define y second

vector < punct > v;
punct mn;
int n,ind;

double det(punct a, punct b, punct c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cmp(punct a,punct b)
{
    return det(v[1],a,b)<0;
}

int main()
{
    f>>n;
    v= vector< punct >(n+1);
    f>>mn.x>>mn.y;
    v[1].x=mn.x;
    v[1].y=mn.y;
    for(int i=2;i<=n;i++)
    {   f>>v[i].x>>v[i].y;
        if(mn.x>v[i].x or(mn.x==v[i].x and mn.y>v[i].y))
        {
            mn=v[i];
            ind=i;
        }
    }
    swap(v[1],v[ind]);
    sort(v.begin()+2,v.end(),cmp);
   int head=2;
    punct st[n+1];
    st[1]=v[1];
    st[2]=v[2];
    for ( int i = 3; i <= n ; i++ )
    {
        while(head>=2 and det(v[i],st[head-1],st[head])>0 ) head--;
        st[++head]=v[i];
    }
    freopen("infasuratoare.out","w",stdout);
    printf("%d\n",head);
    for ( int i = head; i>=1;i--)
    {
        printf("%.8f %.8f\n" , st[i].x , st[i].y) ;
    }
}