Cod sursa(job #1404043)

Utilizator GooggaIoana Iaru Googga Data 27 martie 2015 19:02:05
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point
{
    double x,y;
};
const double eps=1.e-14;

point ll;

double cp(point a, point b, point c)
{
    return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}

int ccw(point a, point b, point c)
{
    double p=cp(a,b,c);
    if(fabs(p)<eps)
           //ABC coliniare
    return 0;
    if(p>=eps)
        //C la stanga lui AB (trigonometric)
        return 1;
    //C la dreapta lui AB (clockwise)
    return -1;
}

double dist(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

bool cmp(const point a,const point b)
{
    int c;
    double d1,d2;
    c=ccw(ll,a,b);
    if(c==0)
    {
        d1=dist(ll,a);
        d2=dist(ll,b);
        if(d1-d2<=-eps)
            return 1;
        else
            return 0;
    }
    if(c==-1)
        return 0;
    return 1;
}

const int NMAX=120010;
point p[NMAX];
int h[NMAX];

int main() {
    int n,i, poz, u, c;
    point aux;
    in>>n;
    ll.x=ll.y=1000000000;
    for(i=0;i<n;i++)
    {
        in>>p[i].x>>p[i].y;
        if(p[i].y-ll.y<=-eps || (fabs(p[i].y-ll.y)<eps && p[i].x-ll.x<=-eps))
        { ll=p[i];
        poz=i;}
    }
    aux=p[0];
    p[0]=p[poz];
    p[poz]=aux;
    
    sort(p+1,p+n,cmp);
    
   p[n]=p[0];
    h[1]=0;
    h[2]=1;
    i=2;
    u=2;
    while(i<=n)
    {
        c=ccw(p[h[u-1]],p[h[u]],p[i]);
        if(c>0)
        {
            h[++u]=i;
            ++i;
        }
        else
            u--;
    }
    u--;
    out<<u<<'\n';
    for(i=1;i<=u;i++)
        out<<setprecision(6)<<fixed<<p[h[i]].x<<" "<<p[h[i]].y<<'\n';
    return 0;
    
}