Cod sursa(job #1280403)

Utilizator danyro364Savu Ioan Daniel danyro364 Data 1 decembrie 2014 22:01:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
//#include <iostream>
#include <algorithm>
#include <cstdio>
#define nmax 120001
#define inf 10000000
using namespace std;
FILE *f=fopen("infasuratoare.in","r"),*g=fopen("infasuratoare.out","w");

struct punct{
double x,y;
}v[nmax],p;
int viz[nmax];

bool det(punct a, punct b, punct c)
{
    return a.x*(b.y-c.y)-a.y*(b.x-c.x)+b.x*c.y-c.x*b.y<0;
}
bool comp(punct a, punct b)
{
    if(a.x<b.x)
        return 1;
    if(a.x==b.x&&a.y<b.y)
        return 1;
    return 0;
}
int main()
{

    int semn=1,st[nmax],poz;
    long n,i,j,k;
    p.x=inf;
    p.y=inf;
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
        {fscanf(f,"%lf %lf",&v[i].x,&v[i].y);
        if(v[i].x<p.x)
            p=v[i],poz=i;
        else if(v[i].x==p.x&&v[i].y<p.y)
            p=v[i],poz=i;
        }
    sort(v+1,v+n+1,comp);
    st[1]=1; st[2]=2;
    k=2;
    viz[2]=1;

    for(i=3;i;i+=semn)
    if(!viz[i])
     {
        while(k>=2&&det(v[st[k-1]],v[st[k]],v[i]))
            viz[st[k--]]=0;

        st[++k]=i;
        viz[i]=1;
        if(i==n)
            semn=-1;
    }
    fprintf(g,"%d\n",k-1);
    for(i=1;i<k;i++)
        fprintf(g,"%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);

    return 0;
}