Cod sursa(job #1382318)

Utilizator BogdacutuSeniuc Bogdan Bogdacutu Data 8 martie 2015 20:25:54
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdio>
using namespace std;
 
#define NMAX 120001
#define EPS 1e-12
 
unsigned long n,h;
struct punct
{
 
    double x,y;
}v[NMAX];
unsigned s[NMAX],ok[NMAX];
 
int semn(punct &a, punct &b, punct &c)
{
    double det=a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - a.x*c.y - b.x*a.y;
    if (det==0) return 0;
    return (det<0)?(-1):1;
}
int cmp1(double a, double b)
{
    if (a+EPS<b) return 1;
    if (b+EPS<a) return -1;
    return 0;
}
int cmp(punct a, punct b)
{
    int t;
    t=cmp1(a.x,b.x);
    if (t!=0) return t==1;
    return (cmp1(a.y,b.y)==1);
}
void citire()
{
    ifstream f("infasuratoare.in");
    f>>n;
    for (unsigned long i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
}
void rezolvare()
{
    s[1]=1; s[2]=2; ok[2]=1;
    long nr_el_stiva=2,nr_pc_infas=1,i=3,contor=1;
    while(!ok[1])
    {
        while (ok[i])
        {
            if (i==n) contor=-1;
            i+=contor;
        }
        while (nr_el_stiva>=2 && semn(v[s[nr_el_stiva-1]],v[s[nr_el_stiva]],v[i])==-1)
            ok[s[nr_el_stiva--]]=0;
        s[++nr_el_stiva]=i;
        ok[i]=1;
    }
    h=nr_el_stiva-1;
}
int main()
{
    freopen("infasuratoare.out","w",stdout);
    citire();
    rezolvare();
    printf("%u\n",h);
    for (unsigned long i=1;i<=h;i++)
        printf("%f %f\n", v[s[i]].x, v[s[i]].y);
    return 0;
}