Cod sursa(job #2193552)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 10 aprilie 2018 14:55:40
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
#define MAXN 120000

int n, last, st[1 + MAXN];
struct Point{double x, y;} v[1 + MAXN];
bool cmpXy(Point A, Point B){return (A.x < B.x || (A.x == B.x && A.y < B.y));}
bool cmpTg(Point A, Point B){
    if(A.x == v[1].x && B.x == v[1].x) return A.y < B.y;
    if(A.x == v[1].x) return 1;
    if(B.x == v[1].x) return 0;
    return (A.x - v[1].x) * (B.y - v[1].y) < (B.x - v[1].x) * (A.y - v[1].y);
}
bool convex(int a, int b, int c){
    float S = (v[a].x * v[b].y + v[b].x * v[c].y + v[c].x * v[a].y) -
              (v[a].x * v[c].y + v[b].x * v[a].y + v[c].x * v[b].y);
    return S < 0;
}

int main(){
    FILE*fi,*fo;
    fi = fopen("infasuratoare.in","r");
    fo = fopen("infasuratoare.out","w");

    fscanf(fi,"%d", &n);
    for(int i = 1; i <= n; i++) fscanf(fi,"%lf%lf", &v[i].x, &v[i].y);
    std::sort(v + 1, v + n + 1, cmpXy);
    std::sort(v + 2, v + n + 1, cmpTg);

    st[++last] = 1, st[++last] = 2;

    for(int i = 3; i <= n; i++){
        while(!convex(st[last - 1], st[last], i))
            last--;
        st[++last] = i;
    }

    fprintf(fo,"%d\n", last);
    for(int i = 1; i <= last; i++)
        fprintf(fo,"%f %f\n", v[st[i]].x, v[st[i]].y);

    return 0;
}