Cod sursa(job #2084068)

Utilizator berindeiChesa Matei berindei Data 8 decembrie 2017 17:02:41
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
using namespace std;
int const INF = 2e9;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct POINT{
    double x, y;
}p[120001], pct, stiva[120001];
POINT BL={INF, INF};
int ls=0;

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) return 0;
    return -1;
}
bool cmp(POINT a, POINT b){
    int c=ccw(BL, a, b);
    if (c==0) return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
    if (c==1) return true;
    else return false;
}
int main(){
    int i, n;
    in >> n;
    for (int i=0; i<=n-1; i++){
        in >> pct.x >> pct.y;
        if (BL.x>pct.x && BL.y>pct.y){
            p[i]={BL.x, BL.y};
            BL={pct.x, pct.y};
        }
        else p[i]={pct.x, pct.y};
    }
    sort(p+1, p+n, cmp);
    p[n]={BL.x, BL.y};
    stiva[1]=p[1];
    stiva[2]=p[2];
    ls=2;
    for (i=3; i<=n; i++){
        while (ccw(stiva[ls-2], stiva[ls-1], p[i])==1) ls--;
        stiva[++ls]={p[i].x, p[i].y};
    }
    out << ls << '\n';
    for (i=1; i<=ls; i++)
        out << stiva[i].x << ' ' << stiva[i].y << '\n';
}