Cod sursa(job #1334689)

Utilizator iuliiaioanaiulia ioana anghel iuliiaioana Data 4 februarie 2015 16:24:51
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct infasuratoare
{
    double x,y;
} v[120001],minp,rasp[120005];
bool det(infasuratoare a, infasuratoare b, infasuratoare c)
{
    if((a.x*b.y +b.x*c.y+c.x*a.y)-(a.y*b.x+b.y*c.x+c.y*a.x) > 0)
        return true;
    else return false;
}
int main()
{
    int n,poz,k=2,j,i;
    float x,y;
    minp.x=1000000001;
    minp.y=1000000001;
    f>>n;
    for( int i=1; i<=n; i++)
    {
        f>>x>>y;
        if(x<minp.x || (x==minp.x && minp.y>y))
        {
            minp.x=x;
            minp.y=y;
            poz=i;
        }
        v[i].x=x;
        v[i].y=y;
    }
    v[poz].x=v[n].x;
    v[poz].y=v[n].y;
    n=n-1;
    for(int i=1; i<n; i++)
        for(j=i+1; j<=n; j++)
        {
            if(det(minp,v[i],v[j]))
                swap(v[i],v[j]);
        }
    rasp[1]=minp;
    rasp[2]=v[1];
    for(i=2; i<=n; i++)
    {
        while(det(rasp[k-1],rasp[k],v[i]))
            k--;
        rasp[++k].x=v[i].x;
        rasp[k].y=v[i].y;
    }
    g<<k<<endl;
    for(i=k; i>=1; i--)
        g<<fixed<<setprecision(6)<<rasp[i].x<<" "<<rasp[i].y<<endl;
    return 0;
}