Cod sursa(job #2375037)

Utilizator Vlad3108Tir Vlad Ioan Vlad3108 Data 7 martie 2019 21:57:46
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;
#define LMAX 120005
#define x first
#define y second
typedef pair<double,double> point;
point p[LMAX];
double det(point a,point b,point c){
    return (a.x*b.y+b.x*c.y+c.x*a.y)-(a.y*b.x+b.y*c.x+c.y*a.x);
}
bool cmp(point a,point b){
    return det(p[1],a,b)>0;
}
int top=0,st[LMAX];
int main(){
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lf %lf",&p[i].x,&p[i].y);
        if(i>1&&p[i]<p[1])
            swap(p[i],p[1]);
    }
    sort(p+2,p+n+1,cmp);
    int top=0;
    for(int i=1;i<=n;++i){
        while(top>1&&det(p[st[top-1]],p[st[top]],p[i])<=0)
            --top;
        st[++top]=i;
    }
    printf("%d\n",top);
    for(int i=1;i<=top;++i)
        printf("%.12f %.12f\n",p[st[i]].x,p[st[i]].y);
    return 0;
}