Cod sursa(job #915536)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 15 martie 2013 09:45:01
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
   
struct point
{
    double x,y;
}v[120001];
   
int n,i,k,p,s[120001],t,j;
double eps=1e-12,minx,miny,mini;
 
double mod (double a)
{
    if (a>0) return a;
    return -a; 
}
   
bool cmp (point A, point B)
{
    return (A.x*B.y>B.x*A.y);
}
   
bool det (point A,point B,point C)
{
    return ((long double )B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y)>=eps;
}
   
int main ()
{
    mini=1; minx=1000000000; miny=1000000000;
    fin>>n;
    for (i=1;i<=n;i++) 
    {
        fin>>v[i].x>>v[i].y;
        if (v[i].y<miny) {mini=i; minx=v[i].x; miny=v[i].y;}
        else if (mod(v[i].y-miny)<=eps) if (v[i].x<minx) {mini=i;minx=v[i].x; miny=v[i].y;}
    }
    for (i=1;i<=n;i++) 
    {
        v[i].x=v[i].x-minx;
        v[i].y=v[i].y-miny;
    }
    sort (v+1,v+n+1,cmp);
    k=0;p=1;
    for (i=1;i<=n;i++)
    {
        s[++k]=i; 
        if (k<3) continue;
        while (k>2&&det(v[s[k]],v[s[k-1]],v[s[k-2]]))
        {
            s[k-1]=s[k];
            k--;
        }
    }
    fout<<k<<"\n";
    for (i=1;i<=k;i++) fout<<fixed<<v[s[i]].x+minx<<" "<<v[s[i]].y+miny<<"\n";
}