Cod sursa(job #475818)

Utilizator S7012MYPetru Trimbitas S7012MY Data 8 august 2010 17:26:56
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define DN 120005

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

int cmp(punct x, punct y) {
    if(x.x<y.x) return 1;
    else if(x.x>y.x) return -1;
    else return x.y<y.y;
}
int pointLocation(punct x, punct y,punct z) {
    int cp1=(y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x);
    return cp1>0;
}

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