Cod sursa(job #2349904)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 20 februarie 2019 20:28:05
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 120007;
const int MAX = 1e9;
	
struct Point
{
    double x, y;
};

Point v[DIM];
Point t[DIM];

double trigo(Point A, Point B, Point C)
{
    return ((B.y - A.y) * (C.x - A.x) - (C.y - A.y) * (B.x - A.x));
}
	
bool cmp(Point A, Point B)
{
    return (trigo(v[1], A, B) > 0);
}
	
int main()
{
	int n;
    in >> n;
	
    int start = 0;
	
	v[start].x = MAX; 
	v[start].y = MAX;
	
    for(int i = 1; i <= n; i++)
	{
        in >> v[i].x >> v[i].y;
	
        if(v[start].x > v[i].x || (v[start].x == v[i].x && v[start].y > v[start].y))
		{
            start = i;
        }
    }
	
    swap(v[start], v[1]);
	
    sort(v + 2, v + n + 1, cmp);
	
	int k = 2;
	
    t[1] = v[1];
    t[2] = v[2];
	
    for(int i = 3; i <= n; i++)
	{
	
        while(k >= 2 && trigo(t[k - 1], t[k], v[i]) < 0)
		{
            k--;
        }
	
        t[++k] = v[i];
    }
	
    out << k << '\n';
	
    for(int i = k; i >= 1; i--)
	{
        out << fixed << setprecision(9) << t[i].x << ' ' << t[i].y << '\n';
    }
}