Cod sursa(job #1124212)

Utilizator vladpopapopa vlad vladpopa Data 26 februarie 2014 11:48:38
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include <fstream>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int l, n, i,ordo, w[120000], k;
float x[120000], y[120000], m[120000], aux;
int isleft( int x1, int y1, int x2, int y2, int x3, int y3)
{
    int val=(x3-x1)*(y2-y1)-(x2-x1)*(y3-y1);
    return val;
}
void arie()
{
    float A;
    for(int i=2; i<=k-1; i++) A+=(x[1]*y[w[i]]+x[w[i]]*y[w[i+1]]+x[w[i+1]]*y[1]-x[1]*y[w[i+1]]-x[w[i]]*y[1]-x[w[i+1]]*y[w[i]])/2;
    g<<A;
}
int main()
{
   f>>n;
   for(i=1; i<=n; i++) f>>x[i]>>y[i];
   /*l=n;
   do{
   ordo=1;
   for(i=1; i<l; i++)
        if(x[i]>x[i+1]) { aux=x[i];
                          x[i]=x[i+1];
                          x[i+1]=aux;
                          aux=y[i];
                          y[i]=y[i+1];
                          y[i+1]=aux;
                          ordo=0;
                        }
     else if(x[i]==x[i+1]) if(y[i]>y[i+1]) {aux=y[i];
                          y[i]=y[i+1];
                                            y[i+1]=aux;
                                            ordo=0;
                                            }

     l--;
   } while(!ordo);*/
   int val=1;
   for(i=1; i<=n; i++) if(x[i]<x[val]) val=i;
                       else if(x[i]==x[val]&&y[val]>y[i]) val=i;
   g<<val<<'\n';
    aux=x[1];
    x[1]=x[val];
    x[val]=aux;
    aux=y[1];
    y[1]=y[val];
    y[val]=aux;
   for(i=2; i<=n; i++)
    {if(x[1]-x[i]) m[i]=((y[1]-y[i])/(x[1]-x[i]));
     else m[i]=1000000;
    }
    l=n;
   do{
   ordo=1;
   for(i=2; i<l; i++)
        if(m[i]>=m[i+1]) { aux=m[i];
                          m[i]=m[i+1];
                          m[i+1]=aux;
                          aux=x[i];
                          x[i]=x[i+1];
                          x[i+1]=aux;
                          aux=y[i];
                          y[i]=y[i+1];
                          y[i+1]=aux;
                          ordo=0;
                        }

     l--;
   } while(!ordo);
   w[1]=1;
   w[2]=2;
   w[3]=3;
   k=3;
   for(i=4; i<=n; i++)
   {   k++;
       w[k]=i;
       while(k>2 && isleft(x[w[k-2]],y[w[k-2]],x[w[k-1]],y[w[k-1]],x[w[k]],y[w[k]])>=0) {k--; w[k]=i;}
   }
  g<<k<<'\n';
   for(int i=1;i<=k;i++)
  g<<x[w[i]]<<" "<<y[w[i]]<<"\n";

  //arie();
    return 0;
}