Cod sursa(job #2137318)

Utilizator Claudiu07Pana Claudiu Claudiu07 Data 20 februarie 2018 18:47:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const double EPS = 1e-12;
int N,H;

struct punct{
double x,y;
}p[120001],sol[120001];

double det(punct a,punct b,punct c)
{
    //return a.x*b.y+a.y*c.x+b.x*c.y-b.y*c.x-a.x*c.y-a.y*b.x;
    return (a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x);
}
int cmp(punct a, punct b)
{
    if(abs(det(p[1],a,b))<EPS)
    {
        return abs(p[1].x-a.x)<abs(p[1].x-b.x);
    }
    if(det(p[1],a,b)<EPS) return 0;
    return 1;
}
void inf_conv()
{
    sort(p+2,p+N+1,cmp);
    H=2;
    sol[1]=p[1];
    sol[2]=p[2];
    for(int i=3; i<=N; i++)
    {
        while(H>=2 && det(sol[H-1],sol[H],p[i])<EPS) H--;
        H++;
        sol[H]=p[i];
    }
}
int main()
{
    f>>N;
    f>>p[1].x>>p[1].y;
    int j=1;
    for(int i=2; i<=N; i++)
        {f>>p[i].x>>p[i].y;
         if(p[i].x<p[j].x) j=i;
         else if(p[i].x==p[j].x && p[i].y<p[j].y) j=i;
        }
    swap(p[1],p[j]);
    inf_conv();
    g<<H<<'\n';
    g<<fixed<<setprecision(6);
    for(int i=1;i<=H;i++)
    {
        g<<sol[i].x<<' '<<sol[i].y<<'\n';
    }

    return 0;
}