Pagini recente » Cod sursa (job #372066) | Cod sursa (job #78917) | Cod sursa (job #3162575) | Cod sursa (job #1861529) | Cod sursa (job #1357665)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <bitset>
#define NMAX 120008
using namespace std;
int n;
struct point{double x, y;};
point a[NMAX];
stack<int> s;
bitset<NMAX> viz;
void read()
{
scanf("%d\n", &n);
for (int i=1; i<=n; ++i)
scanf("%lf %lf\n", &a[i].x, &a[i].y);
}
bool cmp(point A, point B)
{
return A.y < B.y || A.y == B.y && A.x > B.x;
}
double panta(point A, point B)
{
if (B.x == A.x)
return 0;
return -(B.y - A.y) / (B.x - A.x);
}
bool cmp2(point A, point B)
{
double p1 = panta(a[1], A);
double p2 = panta(a[1], B);
if (p1 * p2 <= 0)
return p1 < p2;
return p1 > p2;
}
double det(point A, point B, point C)
{
return A.x * B.y + B.x * C.y + A.y * C.x - B.y * C.x - C.y * A.x - A.y * B.x;
}
void write(int x)
{
if (s.size() == 0)
return;
x = s.top();
s.pop();
write(x);
cout<<a[x].x<<" "<<a[x].y<<"\n";
}
void graham()
{
sort(a+1, a+n+1, cmp);
double aux[NMAX];
for (int i=2; i<=n; ++i)
aux[i] = panta(a[1], a[i]);
sort(a+2, a+n+1, cmp2);
for (int i=2; i<=n; ++i)
aux[i] = panta(a[1], a[i]);
s.push(1);
s.push(2);
int top;
for (int i = 3; i <= n; ++i){
top = s.top();
s.pop();
while (det(a[s.top()], a[top], a[i]) <= 0){
top = s.top();
s.pop();
}
s.push(top);
s.push(i);
}
cout<<s.size()<<"\n";
cout<<fixed<<setprecision(6);
setprecision(13);
write(s.top());
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
read();
graham();
return 0;
}