Cod sursa(job #2386946)

Utilizator herbertoHerbert Mohanu herberto Data 23 martie 2019 22:47:02
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include<bits/stdc++.h>
using namespace std;
#define MAXN 120001

struct punct{
  double x, y;
};

punct v[MAXN], st[MAXN], dr[MAXN], stiv[MAXN], sol[MAXN];
bool cmp(punct a, punct b){
  if(a.y<b.y)
    return 1;
  if(a.y==b.y && a.x<b.x)
    return 1;
  return 0;
}
int dir(punct a, punct b, punct c){//-1 - dreapta, 1 - stanga, 0 - pe dreapta
  double s;
  s=a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
  if(s!=0)
    s=s/(abs(s));
  return s;
}
int n, k1, k2, k;
int main(){
  FILE*fin=fopen("infasuratoare.in", "r");
  FILE*fout=fopen("infasuratoare.out", "w");
  int i;
  fscanf(fin, "%d", &n);
  for(i=1; i<=n; i++)
    fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
  sort(v+1, v+n+1, cmp);
  k1=k2=0;
  for(i=2; i<=n; i++){
//    printf("%d\n", dir(v[1], v[n], v[i]));
    if(dir(v[1], v[n], v[i])<=0){
      k2++;
      dr[k2]=v[i];
    }
    else{
      k1++;
      st[k1]=v[i];
    }
  }
  // pe dreapta
  stiv[1]=v[1];
  stiv[2]=dr[1];
  k=2;
  for(i=2; i<=k2; i++){
    while(k>1 && dir(stiv[k-1], stiv[k], dr[i])==-1)
      k--;
    k++;
    stiv[k]=dr[i];
  }
  int ans=k;
  for(i=1; i<=k; i++){
    sol[i]=stiv[i];
  }
  stiv[1]=v[1];
  stiv[2]=st[1]; k=2;
  for(i=2; i<=k1; i++){
    while(k>1 && dir(stiv[k-1], stiv[k], st[i])==1)
      k--;
    k++;
    stiv[k]=st[i];
  }
  ans+=(k-1);
  fprintf(fout, "%d\n", ans);
  for(i=1; i<=ans-(k-1); i++)
    fprintf(fout, "%lf %lf\n", sol[i].x, sol[i].y);
  for(i=k; i>=2; i--)
    fprintf(fout, "%lf %lf\n", stiv[i].x, stiv[i].y);

//  for(i=1; i<=n; i++)
//    printf("%lf %lf\n", v[i].x, v[i].y);

  return 0;
}