Pagini recente » Cod sursa (job #3250205) | Cod sursa (job #661732) | Cod sursa (job #157496) | Cod sursa (job #1377575) | Cod sursa (job #339504)
Cod sursa(job #339504)
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct PT
{
double x,y;
};
PT a[120001];
double X,Y;
int n,i,low,cnt;
double d(PT a,PT b)
{
return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
bool cmp(PT A,PT B)
{
X = (A.x - a[1].x) / d(A,a[1]);
Y = (B.x - a[1].x) / d(B,a[1]);
return X>Y;
}
bool det(PT a,PT b,PT c)
{
X = a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y);
return X>0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
low = 1;
for(i=1;i<=n;++i)
{
scanf("%lf %lf",&X,&Y);
a[i].x = X;
a[i].y = Y;
if(a[i].y < a[low].y || (a[i].y == a[low].y && a[i].x < a[low].x))
low = i;
}
a[0] = a[low];
a[low] = a[1];
a[1] = a[0];
sort(&a[2],&a[n+1],cmp);
cnt = 2;
for(i=3;i<=n;++i)
{
while(!det(a[cnt-1],a[cnt],a[i]))
--cnt;
a[++cnt] = a[i];
}
printf("%d\n",cnt);
for(i=1;i<=cnt;++i)
printf("%lf %lf\n",a[i].x,a[i].y);
fclose(stdout);
return 0;
}