Cod sursa(job #2101888)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 8 ianuarie 2018 10:45:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <cstdio>
#include <algorithm>
using namespace std;
FILE *f = fopen("infasuratoare.in","r");
FILE *g = fopen("infasuratoare.out","w");
struct punct{
    double x,y;
    bool operator < (const punct &other)const{
        if(x != other.x){
            return x < other.x;
        }
        return y < other.y;
    }
};
double det(punct a,punct b,punct c){
    return a.x * b.y - a.x * c.y + b.x * c.y - b.x * a.y + c.x *a.y - c.x * b.y;
}
punct hull[120005];
punct V[120005];
int N,len;
bool cmp(punct a,punct b){
    if(det(V[1],a,b)){
        return det(V[1],a,b) > 0;
    }
    return a < b;
}
void hullGraham(){
    for(int i = 2;i <= N;i++){
        if(V[i] < V[1]){
            swap(V[i],V[1]);
        }
    }
    sort(V + 2,V + 1 + N,cmp);
    int ind = N;
    while(ind >= 2 && det(V[1],V[ind],V[ind - 1]) == 0){
        ind--;
    }
    if(ind == 1){
        return ;
    }
    reverse(V + ind,V + 1 + N);
    V[N + 1] = V[1];
    for(int i = 1;i <= N + 1;i++){
        while(len > 1 && det(hull[len - 1],hull[len],V[i]) <= 0){
            len--;
        }
        hull[++len] = V[i];
    }
    len--;
}
int main(){
    fscanf(f,"%d",&N);
    for(int i = 1;i <= N;i++){
        fscanf(f,"%lf %lf",&V[i].x,&V[i].y);
    }
    hullGraham();
    fprintf(g,"%d\n",len);
    for(int i = 1;i <= len;i++){
        fprintf(g,"%.6f %.6f\n",hull[i].x,hull[i].y);
    }
    fclose(f);
    fclose(g);
    return 0;
}