Cod sursa(job #1409507)

Utilizator ThomasFMI Suditu Thomas Thomas Data 30 martie 2015 16:05:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

#define x first
#define y second

typedef pair<double, double> Point;

#define NMax 120005
#define eps 1e-12

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n;
Point v[NMax];
bool viz[NMax];
int st[NMax], head;

double cross_product(Point O, Point A, Point B) {
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}

void solve(int i)
{
    while(head >= 2 && cross_product(v[st[head - 1]], v[st[head]], v[i]) < eps)
        viz[st[head--]] = false;
    st[++head] = i;
    viz[i] = true;
}

int main()
{
    int i;

    f>>n;
    for(i=1;i<=n;++i) f>>v[i].x>>v[i].y;

    sort(v+1,v+n+1);

    st[1] = 1; st[2] = 2; head = 2;
    viz[2] = true;

    for(i=3;i<n;++i) if(!viz[i]) solve(i);
    for(i=n;i>=1;--i) if(!viz[i]) solve(i);

    g<<head-1<<"\n";
    g<<setprecision(6)<<fixed;
    for(i=1;i<head;++i) g<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";

    f.close();
    g.close();
}