Cod sursa(job #475834)

Utilizator S7012MYPetru Trimbitas S7012MY Data 8 august 2010 18:53:27
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define DN 120005


struct punct {
    double x; double y;
} siri[DN];
int n;

int cmp(double a,double b) {
    if(a<b) return -1;
    if(b<a) return 1;
    return 0;
}

int cmp_sort(const punct &a,const punct &b) {
    int r=cmp(a.x,b.x);
    if(r) return r==-1;
    return cmp(a.y,b.y)==-1;
}

int pointLocation(punct a, punct b,punct c) {
    double A,B,C;
    A=a.y-b.y;
    B=b.x-a.x;
    C=a.x*b.y-b.x*a.y;
    double rez=A*c.x+B*c.y+C;
    return cmp(rez,0);
}

void in() {
    int ind=1,fol[DN],i=3,stiva[DN],vf=2;
    fol[2]=1; stiva[1]=1; stiva[2]=2;
    while(!fol[1]) {
        while(fol[i] ) {
            if(i==n) ind=-1;
            i+=ind;
        }
        while(vf>=2 && pointLocation(siri[stiva[vf-1]],siri[stiva[vf]],siri[i])==-1) fol[stiva[vf--]]=0;
        stiva[++vf]=i;
        fol[i]=1;
    }
    printf("%d\n",vf-1);
    for(i=1; i<vf; ++i) printf("%.6lf %.6lf\n",siri[stiva[i]].x,siri[stiva[i]].y);
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) scanf("%lf %lf",&siri[i].x,&siri[i].y);
	sort(siri+1,siri+n+1,cmp_sort);
	in();
	return 0;
}