Cod sursa(job #2953610)

Utilizator albertaizicAizic Albert albertaizic Data 11 decembrie 2022 19:31:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX_N=120000;

struct XY{
  double x,y;
};

XY v[MAX_N];
vector <XY> hull;
int n;

inline double orientation(const XY& a, const XY& b, const  XY& c){
  return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}

bool cmp(const XY& a,const XY& b){
  return orientation(v[0],a,b)<0;
}

int findfirst(){
  int j=0,i;

  for(i=1;i<n;i++){
    if(v[j].y<v[i].y || (v[j].y==v[i].y && v[j].x>v[i].x))
      j=i;
  }

  return j;
}

void comphull(){
  int i;

  hull.push_back(v[0]);
  hull.push_back(v[1]);

  for(i=2;i<n;i++){
    while(hull.size()>=2 && orientation(hull[hull.size()-2],hull.back(),v[i])>=0)
      hull.pop_back();
    hull.push_back(v[i]);
  }
}

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

  fscanf(fin,"%d",&n);

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



  swap(v[0],v[findfirst()]);

  sort(v+1,v+n,cmp);

  comphull();

  fprintf(fout,"%d\n", hull.size());
  for(auto k:hull)
    fprintf(fout,"%.12lf %.12lf\n", k.x,k.y);

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