Cod sursa(job #1529083)

Utilizator pufstarDragos Gheorghiu pufstar Data 20 noiembrie 2015 15:14:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define MAX 120005
#define EPS le-12
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in"); ofstream g("infasuratoare.out");
typedef pair <double, double> Point;
Point V[MAX];
inline double Det(Point A, Point B, Point C)
{
    return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}
inline bool cmp(Point A, Point B)
{
    return (Det(V[1], A, B)<0);
}
int n, top, pos, S[MAX];
int main()
{
    f>>n;
    pos=1;
    for(int i=1; i<=n; i++)
    {
        f>>V[i].x>>V[i].y;
        if(V[i]<V[pos]) pos=i;
    }
    swap(V[1], V[pos]);
    sort(V+2, V+n+1, cmp);
    S[++top]=1;
    for(int i=2; i<=n; i++)
    {
        while(top>1 and Det(V[S[top-1]], V[S[top]], V[i])>0) top--;
        S[++top]=i;
    }
    g<<top<<'\n';
    while(top)
    {
        g<<fixed<<setprecision(6)<<V[S[top]].x<<' '<<V[S[top]].y<<'\n';
        top--;
    }
    g.close(); return 0;
}