Cod sursa(job #2339807)

Utilizator TheNextGenerationAyy LMAO TheNextGeneration Data 9 februarie 2019 12:43:20
Problema Infasuratoare convexa Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int N = 120005;
struct Point
{
    double x,y;
} v[N],hull[N];
double sqrDist(Point a, Point b)
{
    double dx = a.x-b.x, dy = a.y-b.y;
    return dx*dx+dy*dy;
}
int orientation(Point a, Point b, Point c)
{
    double val = (b.y-a.y)*(c.x-b.x)-(c.y-b.y)*(b.x-a.x);
    if (val<0)
        return -1;
    if (val>0)
        return 1;
    return 0;
}
Point pivot;
bool comp(Point a, Point b)
{
    int k = orientation(pivot,a,b);
    if (!k)
        return sqrDist(a,pivot)<sqrDist(b,pivot);
    return (k == -1);
}

int main()
{
    int n;
    in >> n;
    for (int i = 1; i<=n; i++)
        in >> v[i].x >> v[i].y;
    pivot = v[1];
    for (int i = 2; i<=n; i++)
        if (v[i].y<pivot.y || (v[i].y == pivot.y && v[i].x<pivot.x))
            pivot = v[i];
    v[1] = pivot;
    sort(v+2,v+n+1,comp);
    hull[1] = v[1]; hull[2] = v[2];
    int head = 2;
    for (int i = 3; i<=n; i++)
    {
        while (head>=2 && orientation(hull[head-1],hull[head],v[i])!=-1)
            head--;
        hull[++head] = v[i];
    }
    out << head << "\n";
    for (int i = 1; i<=head; i++)
        out << fixed << setprecision(10) << hull[i].x << " " << hull[i].y << "\n";
}