Cod sursa(job #2953620)

Utilizator mmocanuMocanu Mihai-Adrian mmocanu Data 11 decembrie 2022 19:40:36
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#define MAXN 120004
#define ERROR 0.000000000001
using namespace std;

struct XY{
  double x,y;
};

XY v[MAXN];
XY comp;
vector <XY> q;

int verf(XY a,XY b,XY c){
  return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}

bool cmp(XY a,XY b){
  return verf(comp,a,b)<0;
}

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

  comp.y=10000000000;
  for(i=0;i<n;i++){
    fscanf(fin,"%lf%lf",&v[i].x,&v[i].y);
    if(comp.x>v[i].x){
      comp=v[i];
    }
  }

  sort(v,v+n,cmp);

  q.push_back(comp);
  q.push_back(v[0]);
  for(i=1;i<n;i++){
    while(verf(q[2],q.back(),v[i])==0 && q.size()>1){
      q.pop_back();
    }
    q.push_back(v[i]);
  }

  fprintf(fout,"%d\n",q.size());
  for(i=0;i<q.size();i++){
    fprintf(fout,"%.12lf %.12lf\n",q[i].x,q[i].y);
  }

  fclose(fin);
  fclose(fout);
  return 0;
}