Cod sursa(job #2158203)

Utilizator berindeiChesa Matei berindei Data 10 martie 2018 11:16:51
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;
int const INF=2e9;
int const NMAX=120000;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

struct POINT{
    double x, y;
}p[NMAX+20], LL, pct, stiva[NMAX+20];

int ls;

int ccw(POINT a, POINT b, POINT c){
    int cp=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    if (cp>0) return 1;
    else if (cp==0) return 0;
    return -1;
}

bool cmp(POINT a, POINT b){
    int c=ccw(LL, a, b);
    if (c==1) return true;
    if (c==0) return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
    return false;
}

int main(){
    int i, n;
    in >> n;
    LL={INF, INF};
    for (int i=0; i<=n-1; i++){
        in >> pct.x >> pct.y;
        if (LL.y>pct.y){
            p[i]=LL;
            LL=pct;
        }
        else if (LL.y==pct.y && LL.x>pct.y){
            p[i]=LL;
            LL=pct;
        }
        else p[i]=pct;
    }
    sort(p+1, p+n, cmp);
    p[n]=LL;
    stiva[1]=LL;
    stiva[2]=p[1];
    ls=2;
    for (i=2; i<=n; i++){
        while (ls>=2 && ccw(stiva[ls-1], stiva[ls], p[i])==-1) ls--;
        stiva[++ls]=p[i];
    }
    out << ls-1 << '\n';
    for (i=1; i<=ls-1; i++)
        out << stiva[i].x << ' ' << stiva[i].y << '\n';
}