Cod sursa(job #2084283)

Utilizator leraValeria lera Data 8 decembrie 2017 21:31:25
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>
#define x first
#define y second
#define Nmax 120005
using namespace std;

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

int sol[Nmax], n, k;
pair<double, double>p[Nmax];

bool cmp(pair<double, double>a, pair<double, double>b)
{
    if(a.x == b.x)return a.y < b.y;
    return a.x < b.x;
}
double det(int a, int b, int c)
{
    return (p[b].x - p[a].x) * (p[c].y - p[a].y) - (p[c].x - p[a].x) * (p[b].y - p[a].y);
    //return (p[a].x * (p[b].y - p[c].y) - p[a].y * (p[b].x - p[c].x) + p[b].x * p[c].y - p[b].y * p[c].x);
}
int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> p[i].x >> p[i].y;

    sort(p + 1, p + n + 1, cmp);
   // for(int i = 1; i <= n ; i++)fout << p[i].x << " "<< p[i].y << '\n';
    sol[1] = 1; sol[2] = 2;
    k = 2;
    for(int i = 3; i <= n; i++)
    {
        while(k > 1 && det(sol[k - 1], sol[k], i) > 0)k--;
        sol[++k] = i;
    }
    for(int i = n - 1; i >= 1; i--)
    {
        while(k > 1 && det(sol[k - 1], sol[k], i) > 0)k--;
        sol[++k] = i;
    }
    fout << k - 1 << '\n';
    for(int i = 1; i < k; i++)
        fout << fixed << setprecision(12) << p[sol[i]].x << " " << p[sol[i]].y << '\n';
    return 0;
}