Pagini recente » Cod sursa (job #1717562) | Cod sursa (job #81526) | Cod sursa (job #728881) | Cod sursa (job #3264121) | Cod sursa (job #411903)
Cod sursa(job #411903)
#include<stdio.h>
#include<algorithm>
using namespace std;
#define nmax 120010
#define inf 1000000010
int s[nmax], k, n, i, pmin;
struct coord
{ double x, y;
} a[nmax], m, z;
int panta_min(coord p1, coord p2)
{ double tmp1, tmp2;
tmp1=(p1.y-m.y)*(p2.x-m.x)-(p2.y-m.y)*(p1.x-m.x);
// tmp2=(p1.x-m.x)*(p2.x-m.x);
if(tmp1<0) return 1;
else return 0;
}
int panta()
{ coord A, B, C;
double tmp1, tmp2;
A=a[s[k-1]]; B=a[s[k]]; C=a[i];
tmp1=(C.y-A.y)*(B.x-A.x)-(C.x-A.x)*(B.y-A.y);
// tmp2=(C.x-A.x)*(B.x-A.x);
if(tmp1<0) return 1;
else return 0;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
m.x=inf; m.y=inf;
for(i=1; i<=n; i++)
{ scanf("%lf%lf", &a[i].x, &a[i].y);
if(m.x>a[i].x || (m.x==a[i].x && m.y>a[i].y)) {m.x=a[i].x; m.y=a[i].y; pmin=i;}
}
z=a[1]; a[1]=a[pmin]; a[pmin]=z;
sort(a+2, a+n+1, panta_min);
s[1]=1; s[2]=2; k=2;
for(i=3; i<=n; i++)
{ while(panta() && k>=2) k--;
k++; s[k]=i;
}
printf("%d\n", k);
for(i=1; i<=k; i++)
printf("%lf %lf\n", a[s[i]].x, a[s[i]].y);
return 0;
}