Pagini recente » Cod sursa (job #2009147) | Istoria paginii utilizator/1475369147896537415369 | Cod sursa (job #2684556) | Istoria paginii utilizator/1475369147896537415369 | Cod sursa (job #1887764)
#include <iostream>
#include <cstdio>
#include <stack>
#define NMAX 1000005
using namespace std;
int n, pozMin=1;
struct puncte
{
double x, y;
}v[120005], minim;
stack <double> s;
void read()
{
scanf("%d", &n);
minim.x=NMAX;
minim.y=NMAX;
for(int i=1; i<=n; ++i)
{
scanf("%lf %lf", &v[i].x, &v[i].y);
if(v[i].x < v[pozMin].x || (v[i].x==v[pozMin].x && v[i].y < v[pozMin].y))
{
swap(v[i], v[pozMin]);
pozMin=i;
}
}
}
double calcDet(int a, int b, int c)
{
return (double) v[b].x*v[c].y + v[c].x*v[a].y + v[a].x*v[b].y - v[b].x*v[a].y - v[c].x*v[b].y - v[a].x*v[c].y;
}
void sortarePuncte()
{
for(int i=2; i<n; ++i)
for(int j=i+1; j<=n; ++j)
{
if(calcDet(1, i, j)<0)
swap(v[i], v[j]);
}
}
void solve()
{
sortarePuncte();
int k=0, ant1, ant2;
s.push(1);
ant2=s.top();
s.push(2);
ant1=s.top();
for(int i=3; i<=n; ++i)
{
while(calcDet(ant2, ant1, i)<0)
{
s.pop();
ant1=s.top();
s.pop();
ant2=s.top();
s.push(ant1);
}
s.push(i);
swap(ant1, ant2);
ant1=i;
}
printf("%d\n", s.size());
while(!s.empty())
{
printf("%.2lf %.2lf\n", v[s.top()].x, v[s.top()].y);
}
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
//freopen("infasuratoare.out", "w", stdout);
read();
solve();
return 0;
}