Cod sursa(job #2953604)

Utilizator mmocanuMocanu Mihai-Adrian mmocanu Data 11 decembrie 2022 19:23:22
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 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;

bool cmp(XY a,XY b){
  if((a.y-comp.y)*(b.x-comp.x)<(b.y-comp.y)*(a.x-comp.x)){
    return 1;
  }else{
    if((a.y-comp.y)*(b.x-comp.x)>(b.y-comp.y)*(a.x-comp.x)){
      return 0;
    }else{
      if(a.x<b.x){
        return 1;
      }else{
        return 0;
      }
    }
  }
}

bool verf(XY a,XY b,XY c){
  int aux=(b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
  if(aux>0){
    return 0;
  }
  return 1;
}

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

  comp.x=-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-1;i++){
    while(verf(q[q.size()-2],q.back(),v[i])==0){
      q.pop_back();
    }
    q.push_back(v[i]);
  }

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

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