Cod sursa(job #2515650)

Utilizator andra1782Andra Alazaroaie andra1782 Data 29 decembrie 2019 01:45:52
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <algorithm>
#define MAX 120000

struct punct{
  double x,y;
}v[MAX];
int f,q[MAX];

bool cross_product(punct a, punct b, punct c){
  return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y)>0;
}

bool comp(punct a, punct b){
  return cross_product(v[f],a,b);
}

int main(){
    FILE *fin=fopen("infasuratoare.in","r");
    FILE *fout=fopen("infasuratoare.out","w");
    int n,i;

    fscanf(fin,"%d ",&n);
    for(i=0; i<n; i++){
      fscanf(fin,"%lf%lf",&v[i].x,&v[i].y);
      if(v[i].y<v[f].y || (v[i].y==v[f].y && v[i].x<v[f].x))
        f=i;
    }
    punct aux=v[f];
    v[f]=v[0];
    v[0]=aux;
    std::sort(v+1,v+n,comp);
    q[1]=1;
    int k=2;
    for(i=2; i<n; i++){
      while(!cross_product(v[q[k-2]],v[q[k-1]],v[i]))
        k--;
      q[k++]=i;
    }
    fprintf(fout,"%d\n",k);
    for(i=0; i<k; i++)
      fprintf(fout,"%f %f\n",v[q[i]].x,v[q[i]].y);
    fclose(fin);
    fclose(fout);
    return 0;
}