Cod sursa(job #801468)

Utilizator alex45meOlaru Alex alex45me Data 24 octombrie 2012 14:48:19
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

struct point{double x,y;};
int n,i,j,st[120000],kk;
point v[120000],mn,aux;

bool cmp(point a,point b)
{
    return ((a.y-mn.y)*(b.x-mn.x)<=(a.x-mn.x)*(b.y-mn.y));
}

bool smn(point a,point b,point c)
{
    double s;
    s=(long double)a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
    if (s<=0) return 0;
    if (s>0) return 1;
}
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");



int main()
{
     fscanf(f,"%d",&n);
     fscanf(f,"%lf%lf",&v[1].x,&v[1].y);
     mn=v[1];
     for (i=2;i<=n;i++)

     {
                    fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
                    if (v[i].x<mn.x){
                            mn=v[i];
                            kk=i;}
                        else  if (v[i].x==mn.x )

                        if (v[i].y>mn.y){ mn=v[i];kk=i;}
     }
      aux=v[1];
      v[1]=mn;
      v[kk]=aux;

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

     st[0]=2;
     st[1]=1;
     st[2]=2;
     i=1;
     for (i=3;i<=n;i++)
        {

         while (!smn(v[st[st[0]-1]],v[st[st[0]]],v[i])&& st[0]>=1) st[0]--;
         st[0]++;
         st[st[0]]=i;

                }
       fprintf(g,"%d\n",st[0]);
        for (i=1;i<=st[0];i++) fprintf(g,"%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
    return 0;
}