Cod sursa(job #1921015)

Utilizator ButmalaiDanButmalai Dan ButmalaiDan Data 10 martie 2017 11:05:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<bits/stdc++.h>
using namespace std;
int n, st = 2;
struct dot{double x,y;};
dot A[120100], sta[120100];
double f(dot a, dot b, dot c)
{
	return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}
bool comp(dot a, dot b)
{
	return (f(A[1],a,b) < 0);
}
int main()
{
	ifstream cin("infasuratoare.in");
	ofstream cout("infasuratoare.out");
	cin >> n;
	int poz = 1;
	for(int i = 1; i <= n; i++)
	{
		cin >> A[i].x >> A[i].y;
		if (A[i].x < A[poz].x || (A[i].x == A[poz].x && A[i].y < A[poz].y)) poz = i;
	}
	swap(A[1], A[poz]);
	sort(A+2,A+n+1, comp);
	sta[1] = A[1]; sta[2] = A[2];
	for (int i = 3; i <= n; i++)
	{
		while(st >= 2 && f(sta[st-1],sta[st],A[i]) > 0) st--;
		st++;
		sta[st] = A[i];
	}
	cout << st << "\n";
	while(st)
	{
		cout<< setprecision(13) << fixed << sta[st].x << " " << sta[st].y << "\n";
		st--;
	}
}