Pagini recente » Cod sursa (job #2289484) | Cod sursa (job #2299539) | Cod sursa (job #2944914) | Cod sursa (job #1689068) | Cod sursa (job #1716791)
#include <cstdio>
#include <cmath>
#include <algorithm>
#define NMAX 120000
const double eps=1.e-12;
struct POINT{
double x, y;
}p[NMAX+5], LL;
int st[NMAX+5];
double cp(POINT P1, POINT P2, POINT P3){
return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x);
}
int ccw(POINT P1, POINT P2, POINT P3){
double cpp;
cpp=cp(P1, P2, P3);
if (fabs(cpp)<eps)
return 0; //coliniare
if (cpp>=eps)
return 1; //sens trigonometric
return -1; //sens orar
}
bool cmp(POINT P1, POINT P2){
return (ccw(LL, P1, P2)>0);
}
int main(){
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n, i, top;
scanf("%d", &n);
scanf("%lf%lf", &p[0].x, &p[0].y);
LL=p[0];
for (i=1; i<n; i++){
scanf("%lf%lf", &p[i].x, &p[i].y);
if ((p[i].y-LL.y<=-eps)||(fabs(p[i].y-LL.y)<eps && p[i].x-LL.x<=-eps)){
LL=p[i];
p[i]=p[0];
p[0]=LL;
}
}
std::sort(p+1, p+n, cmp);
p[n]=p[0];
st[0]=0; st[1]=1;
top=1;
i=2;
while (i<=n)
if (ccw(p[st[top-1]], p[st[top]], p[i])>0){
st[++top]=i;
i++;
}else top--;
printf("%d\n", top);
for (i=0; i<top; i++)
printf("%.6lf %.6lf\n", p[st[i]].x, p[st[i]].y);
return 0;
}