Cod sursa(job #363879)

Utilizator APOCALYPTODragos APOCALYPTO Data 14 noiembrie 2009 21:57:04
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb

#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<iomanip>
using namespace std;
struct data{
    double x;
    double y;
    long mark;
    long ind;
    long index;
};
data pct[120000],aux;
long n;

bool compare(data i,data j)
{return ((i.x-pct[1].x)*(j.y-pct[1].y)<(i.y-pct[1].y)*(j.x-pct[1].x));
}
int main()
{vector<int> stiva;
int k,i,u,w;
long min=1;



ifstream fin("infasuratoare.in");

    fin>>n;
    for(i=1;i<=n;i++)
      {fin>>pct[i].x>>pct[i].y;
      pct[i].ind=i;
}

fin.close();
    for(i=2;i<=n;i++)
       {if(pct[i].x<pct[min].x)
       min=i;}

    aux=pct[min];
    pct[min]=pct[1];
    pct[1]=aux;
    sort(pct+2,pct+n+1,compare);
    for(i=1;i<=n;i++)
      pct[i].index=i;
    stiva.push_back(0);
    stiva.push_back(pct[1].index);
    stiva.push_back(pct[2].index);
    stiva.push_back(pct[3].index);

    k=3;
    u=stiva[k-1];
    w=stiva[k];
    for(i=4;i<=n;i++)
        {while(k>2&&((pct[w].x - pct[u].x)*(pct[i].y - pct[u].y)-(pct[w].y - pct[u].y)*(pct[i].x - pct[u].x)>0))
        //(pct[u].x * pct[w].y + pct[w].x * pct[i].y + pct[i].x * pct[u].y - pct[u].y * pct[w].x - pct[w].y * pct[i].x - pct[i].y * pct[u].x)>0)
        //(pct[k].x - pct[k-1].x)*(pct[i].y - pct[k-1].y)<(pct[k].y - pct[k-1].y)*(pct[i].x - pct[k-1].x))
           {k=k-1;
            u=stiva[k-1];
            w=stiva[k];
            stiva.pop_back();

           }

         k=k+1;
         u=stiva.back();
         w=pct[i].index;
         stiva.push_back(pct[i].index);
        }

  ofstream fout("infasuratoare.out");
  for (i=1; i<=k; i++)
    {
        fout<<fixed<<setprecision(12)<<pct[pct[stiva[i]].ind].x<< " " << pct[pct[stiva[i]].ind].y;
    fout <<'\n';}
  fout.close();


    return 1;
}