Pagini recente » Cod sursa (job #1232453) | Cod sursa (job #1253887) | Cod sursa (job #2855833) | Cod sursa (job #758357) | Cod sursa (job #294858)
Cod sursa(job #294858)
#include <cstdio>
#define dim 120100
using namespace std;
int n, s[dim], k;
double x[dim], y[dim];
long double semn(int n1, int n2, int n3)
{
return (long double)x[n1]*y[n2]+x[n2]*y[n3]+x[n3]*y[n1]-y[n1]*x[n2]-y[n2]*x[n3]-y[n3]*x[n1];
}
void graham()
{
int i;
s[0]=1;
s[1]=2;
s[2]=3;
k=2;
for (i=4; i<=n; i++)
{
while (semn(s[k-1], s[k], i)<=0)
k--;
s[++k]=i;
}
}
void swap(double &a, double &b)
{
double t=a;
a=b;
b=t;
}
int comp(int n1, int n2)
{
double a, b;
a=(y[n1]-y[1])*(x[n2]-x[1]);
b=(y[n2]-y[1])*(x[n1]-x[1]);
if (a<b) return -1;
if (a==b) return 0;
return 1;
}
void sort(int lo, int hi)
{
int i=lo, j=hi, m=i+(j-i)/2;
do
{
while (comp(i, m)<0) i++;
while (comp(m, j)<0) j--;
if (i<=j)
{
swap(x[i], x[j]);
swap(y[i], y[j]);
i++, j--;
}
} while(i<=j);
if (lo<j) sort(lo, j);
if (i<hi) sort(i, hi);
}
int main()
{
int i, in;
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d\n", &n);
for (i=1; i<=n; i++) scanf("%lf %lf\n", &x[i], &y[i]);
in=1;
for (i=2; i<=n; i++)
if ((y[i]<y[in]) || (y[i]==y[in] && x[i]<x[in])) in=i;
if (in!=1)
{
swap(x[1], x[in]);
swap(y[1], y[in]);
}
sort(2, n);
graham();
printf("%d\n", k+1);
for (i=0; i<=k; i++) printf("%lf %lf\n", x[s[i]], y[s[i]]);
return 0;
}