Cod sursa(job #1716791)

Utilizator raluca1234Tudor Raluca raluca1234 Data 13 iunie 2016 19:06:21
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#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;
}