Cod sursa(job #2376039)

Utilizator radumihaisirbuSirbu Radu-Mihai radumihaisirbu Data 8 martie 2019 13:26:37
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

#define x first
#define y second

const int NMAX = 120005;

pair <double, double> v[NMAX];


double low_point, low_pointy;

int n, top, st[NMAX];

double det (pair <double, double> A, pair <double, double> B, pair <double, double> C)
{
    return -(C.x * B.y + A.y * B.x + C.y * A.x) + (C.x * A.y + A.x * B.y + C.y * B.x);
}

bool cmp (pair <double, double> A, pair <double, double> B)
{
    return det(v[1], A, B) > 0;
}

int main()
{
    fin >> n;
    for (int i=1; i<=n; i++)
    {
        fin >> v[i].x >> v[i].y;
        if (i > 1)
            if (v[i].x < v[1].x) swap(v[1], v[i]);
            else if (v[i].x == v[1].x && v[i].y < v[1].y) swap(v[1], v[i]);
    }
    sort(v+2,v+n+1,cmp);
   // for (int i=1; i<=n; i++)
        //cout << v[i].x << " " << v[i].y << "\n";
    for (int i=1; i<=n; i++)
    {
        while (top > 1 && det(v[st[top-1]], v[st[top]], v[i]) <= 0) top--;
        st[++top] = i;
    }
    fout << top << "\n";
    for (int i=top; i>=1; i--)
        fout << v[st[i]].x << " " << v[st[i]].y << "\n";
    return 0;
}