Cod sursa(job #1723482)

Utilizator refugiatBoni Daniel Stefan refugiat Data 30 iunie 2016 18:56:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>
//#include <iostream>
#include <algorithm>
#define punct pair<double,double>
#define mkp make_pair
#define x first
#define y second
using namespace std;
FILE*si=fopen("infasuratoare.in","r");
FILE*so=fopen("infasuratoare.out","w");
punct v[120005];
punct inf[120005];
double det(punct a,punct b,punct c)
{
    return (a.x-b.x)*(a.y-c.y)-(a.x-c.x)*(a.y-b.y);
}
bool comp(punct a,punct b)
{
    return (det(v[1],a,b)>0);
}
int main()
{
    int n;
    fscanf(si,"%i",&n);
    int i;
    for(i=1;i<=n;++i)
    {
        fscanf(si,"%lf %lf",&v[i].x,&v[i].y);
    }
    for(i=2;i<=n;++i)
    {
        if(v[i]<v[1])
        {
            swap(v[i],v[1]);
        }
    }
    sort(v+2,v+n+1,comp);
    int sol=2;
    inf[1]=v[1];
    inf[2]=v[2];

    for(i=3;i<=n;++i)
    {
        while(sol>=2&&(det(inf[sol-1],inf[sol],v[i])<0))
            --sol;
        ++sol;
        inf[sol]=v[i];
    }
    fprintf(so,"%i\n",sol);
    for(i=1;i<=sol;++i)
    {
        //cout<<inf[i].x<<' '<<inf[i].y<<'\n';
        fprintf(so,"%.6f %.6f\n",inf[i].x,inf[i].y);

    }
    fclose(so);
    return 0;
}