Cod sursa(job #2700848)

Utilizator BogdanTicuTicu Bogdan Valeriu BogdanTicu Data 29 ianuarie 2021 02:21:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;
 
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
 
 
struct Punct
{
	double x, y;
};
 
Punct P[120005];
int St[120005];
bool viz[120005];
 
double det(const Punct &a, const Punct &b, const Punct &c)
{
	return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
}
 
bool ok(const Punct &a, const Punct &b)
{
	if(a.x==b.x)
		return a.y<b.y;
	return a.x<b.x;
}
 
void solve(int &n,int &h)
{
	sort(P + 1, P + n + 1, ok);
	St[1] = 1;
	St[2] = 2;
	h=2;
    	viz[2] = 1;
    	for(int i = 3, p = 1; i >= 1; i += p)
    	{
        	if(viz[i]) continue;
        	while(h >= 2 && det(P[St[h - 1]], P[St[h]], P[i]) < 0)
            		viz[St[h--]]=0;
        	St[++h]=i;
        	viz[i] = 1;
        	if(i==n)
            		p = -1;
    	}
   	 h--;
}
 
int main()
{
	int n,h;
	in >> n;
	for(int i = 1; i <= n; i++)
        	in >> P[i].x >> P[i].y;
	solve(n,h);
	out << h << '\n';
	out<< fixed << setprecision(6);
	for(int i = 1; i <= h; i++)
        	out << P[St[i]].x << ' ' <<P[St[i]].y << '\n';
    	return 0;
}