Cod sursa(job #2136669)

Utilizator Claudiu07Pana Claudiu Claudiu07 Data 20 februarie 2018 09:18:05
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#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;
}
int cmp(punct a, punct b)
{
    if(det(p[1],a,b)<EPS) return 0;
    return 1;
}
void inf_conv()
{
    sort(p+1,p+N+1,cmp);
     H=2;
    sol[1]=p[1];
    sol[2]=p[2];
    for(int i=3; i<=N; i++)
    {
        while(det(sol[H-1],sol[H],p[i])<EPS) H--;
        H++;
        sol[H]=p[i];
    }
}
int main()
{
    f>>N;
    int j=1;
    for(int i=1; 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;
}