Cod sursa(job #2156300)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 8 martie 2018 17:11:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct punct{
  double x,y;
};
bool cmp(punct a,punct b){
  if(a.x<b.x)
    return true;
  if(a.x==b.x)
    if(a.y<b.y)
      return true;
  return false;
}
bool semnarie(punct p1,punct p2,punct p3){
  return (p2.x*p1.y + p3.x*p2.y + p1.x*p3.y - p1.x*p2.y - p2.x*p3.y -p3.x*p1.y)<0;
}
punct v[120005];
punct stiva [120005];
punct vectorsol[120005];
int main()
{
    FILE*fin,*fout;
    int n,i;
    fin=fopen("infasuratoare.in","r");
    fout=fopen("infasuratoare.out","w'");
    fscanf(fin,"%d",&n);
    for(i=0;i<n;i++)
      fscanf(fin,"%lf%lf",&v[i].x,&v[i].y);
    sort(v,v+n,cmp);
    int vf=0;
    stiva[++vf]=v[0];
    for(i=1;i<n;i++){
      while(vf>1 && !semnarie(stiva[vf-1],stiva[vf],v[i]))
        vf--;
      stiva[++vf]=v[i];
    }
    int cvf=vf;
    for(i=1;i<=vf;i++){
      vectorsol[i]=stiva[i];
    }
    vf=0;
    stiva[++vf]=v[n-1];
    for(i=n-2;i>=0;i--){
      while(vf>1 && !semnarie(stiva[vf-1],stiva[vf],v[i]))
        vf--;
      stiva[++vf]=v[i];
    }
    for(i=2;i<=vf;i++){
      vectorsol[i+cvf-1]=stiva[i];
    }
    cvf+=vf;
    cvf-=2;
    fprintf(fout,"%d\n",cvf);
    for(i=1;i<=cvf;i++)
      fprintf(fout,"%lf %lf\n",vectorsol[i].x,vectorsol[i].y);
    return 0;
}