Cod sursa(job #475823)

Utilizator S7012MYPetru Trimbitas S7012MY Data 8 august 2010 18:07:27
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 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 0;
    else {
        if(x.y<y.y) return -1;
        else if(x.y>y.y) return 1;
        return 0;
    }
}
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;
    double rez=A*c.x+B*c.y+C;
    if(rez <0) return -1;
    if(rez>0) return 1;
    return 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);
}

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;
}