Cod sursa(job #249431)

Utilizator katakunaCazacu Alexandru katakuna Data 28 ianuarie 2009 14:02:09
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<stdio.h>
#define INF 1<<30
#include<algorithm>
using namespace std;

struct coord  {long double x,y,tg;} aux,v[120111];
int p,n,i,s[120111];
long double xmin,ymin;

int poz( long double x1, long double y1, long double x2, long double y2, long double x3, long double y3 ){
long double S;

S=(x3-x1)*(y2-y1)-(x2-x1)*(y3-y1);

if(S >= 0)
return -1;

return 1;
}

int cmp(coord a, coord b){
return a.tg < b.tg;
}

int main(){

FILE *f=fopen("infasuratoare.in","r");
fscanf(f,"%d",&n);

ymin = xmin = INF;

  for(i = 1; i <= n; i++){
  fscanf(f,"%Lf %Lf",&v[i].x,&v[i].y);
    if(v[i].x < xmin || (v[i].x == xmin && v[i].y < ymin)){
    xmin = v[i].x;
    ymin = v[i].y;
    p=i;
    }
  }

fclose(f);

aux=v[n];
v[n]=v[p];
v[p]=aux;


  for(i = 1; i < n; i++){
  v[i].x-= xmin;
  v[i].y-= ymin;
  v[i].tg = v[i].y / v[i].x;
  }

v[n].x-= xmin;
v[n].y-= ymin;

sort(v + 1, v + n, cmp);
s[++s[0]] = n;

   for(i = 1; i < n; i++){
   s[++s[0]]=i;
      while(poz( v[s[s[0] - 1]].x, v[s[s[0] - 1]].y, v[s[s[0]]].x, v[s[s[0]]].y, v[s[s[0] - 2]].x, v[s[s[0] - 2]].y ) == -1 && s[0] > 2){
      s[0]--;
      s[s[0]] = s[s[0] + 1];
      }
      
   }

FILE *g=fopen("infasuratoare.out","w");
fprintf(g, "%d\n", s[0]);

  for(i = 1; i <= s[0]; i++){
  fprintf(g, "%Lf %Lf\n", v[s[i]].x + xmin, v[s[i]].y + ymin);
  }
  
fclose(g);

return 0;
}