Cod sursa(job #2955692)

Utilizator teochess2017Togan Teodor-Bogdan teochess2017 Data 17 decembrie 2022 17:08:20
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.78 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAXN 120000
#define INF 1000000000
#define EPSILON 0.000000000001

struct coord{
    double x, y;
};
coord v[MAXN];
int out[MAXN];

double modul(double a){
  if(a < 0){
    return -a;
  }else{
    return a;
  }
}

bool Verificare_Unghi_Convex(coord lastlast, coord last, coord next){
  double a, b, intersectiex;
  if(modul(last.y - lastlast.y) < EPSILON){
    if(lastlast.x < last.x){
      if(last.y < next.y){
        return true;
      }else{
        return false;
      }
    }else{
      if(next.y < last.y){
        return true;
      }else{
        return false;
      }
    }
  }else if(modul(last.x - lastlast.x) < EPSILON){
    if(lastlast.y < last.y){
      if(next.x < last.x){
        return true;
      }else{
        return false;
      }
    }else{
      if(last.x < next.x){
        return true;;
      }else{
        return false;
      }
    }
  }else{
    a = (last.y - lastlast.y) / (last.x - lastlast.x);
    b = last.y - (a * last.x);
    intersectiex = (next.y - b) / a;
    if(lastlast.y < last.y){
      if(intersectiex < next.x){
        return false;
      }else{
        return true;
      }
    }else{
      if(next.x < intersectiex){
        return false;
      }else{
        return true;
      }
    }
  }
}
bool cmp(coord a, coord b){
  double tg0a, tg0b;
  if(a.y == v[0].y){
    if(a.x < v[0].x){
      return true;
    }else{
      return false;
    }
  }else if(b.y == v[0].y){
    if(b.x < v[0].x){
      return false;
    }else{
      return true;
    }
  }else{
    tg0a = (a.x - v[0].x) / (a.y - v[0].y);
    tg0b = (b.x - v[0].x) / (b.y - v[0].y);
    if(tg0b < tg0a){
      return true;
    }else{
      return false;
    }
  }
}

int main()
{
    FILE *fin, *fout;
    int n, i, inext, min, u, io;
    fin = fopen("infasuratoare.in", "r");
    fscanf(fin, "%d", &n);
    min = INF;
    for(i = 0; i < n; i++){
        fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
        if(v[i].y < min){
            min = v[i].y;
            io = i;
        }
    }
    fclose(fin);
    swap(v[io], v[0]);
    sort(v + 1, v + n, cmp);
    out[0] = 1;
    out[1] = 2;
    u = 2;
    inext = 3;
    while((inext % n) != io){
        if(Verificare_Unghi_Convex(v[out[u - 1]], v[out[u - 2]], v[inext])){
            out[u - 1] = inext;
        }else{
            out[u] = inext;
            u++;
        }
        inext++;
    }
    fout = fopen("infasuratoare.out", "w");
    fprintf(fout, "%d\n", u + 1);
    fprintf(fout, "%0.6lf %0.6lf\n", v[0].x, v[0].y);
    for(i = 0; i < u; i++){
      fprintf(fout, "%0.6lf %0.6lf\n", v[out[i]].x, v[out[i]].y);
    }
    fclose(fout);
    return 0;
}