Cod sursa(job #1827432)

Utilizator TibiraducanuTiberiu Raducanu Tibiraducanu Data 11 decembrie 2016 20:25:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

const int N=120005;
const double eps=1e-12;
int i,n,st[N];

struct Point{
	double x,y;
} v[N];

bool cmp(Point a, Point b){
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}

double cross_product(Point P1, Point P2, Point P3){
	return (P2.x-P1.x)*(P3.y-P1.y)-(P2.y-P1.y)*(P3.x-P1.x);
}

int ccw(Point P1,Point P2,Point P3){
	double cp=cross_product(P1,P2,P3);
	if(fabs(cp)<eps) return 0;
	if(cp>eps) return 1;
	return -1;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%lf%lf",&v[i].x,&v[i].y);
    sort(&v[1],&v[n+1],cmp);

    int pos=2,r=1;
    st[1]=1, st[2]=2;
    for(i=3;i>0;i+=r){
        if(i==n) r=-1;
        while(pos>=2 and ccw(v[st[pos-1]], v[st[pos]], v[i])==-1) pos--;
        st[++pos]=i;
    }

    pos--;
    printf("%d\n",pos);
    for(i=1;i<=pos;i++) printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);

    return 0;
}