Cod sursa(job #1538926)

Utilizator lucamateiLuca Matei lucamatei Data 30 noiembrie 2015 00:31:26
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

struct punct{float x,y;};
punct p,q,r,v[100] ;
int n,i,j,jj,viz[100],st[100];

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
bool ff(punct p1, punct p2)//ordonate dupa x si la x egal dupa y
{
   if (p1.x != p2.x) return p1.x < p2.x ;
    else return p1.y < p2.y ;
}

int viraj(punct p, punct q, punct r)
{

   //Returns -1, 0, 1 daca p,q,r la dreapta , pe linie , la stanga
    return (q.x - p.x)*(r.y - p.y) - (r.x - p.x)*(q.y - p.y);
}
int main()
{
   // citesc n puncte in plan
   f>>n;    for(i=1;i<=n;i++)    f>>v[i].x>>v[i].y;

  //sortez dupa x si la x egal dupa y
  sort(v+1,v+n+1,ff);

 //for(i=1;i<=n;i++)    g<<v[i].x<<" "<<v[i].y<<endl;// afisare sortare

st[1]=1;
st[2]=2;
viz[1]=viz[2]=1;
j=2;
  for(i=3;i<=n;i++)
    { //g<<v[i].x<<"kk "<<v[i].y<<endl;
     while(viraj(v[st[j-1]],v[st[j]],v[i])<1&&j>1){//g<<viraj(v[st[j-1]],v[st[j]],v[i])<<endl;
     viz[st[j]]=0;j--;}//cat timp  punctul i se afla in dreapta sau coliniar
     j++;st[j]=i; viz[i]=1;
     }// punctul se afla in stanga si fac viraj stanga
     //   g<<j<<" "<<v[st[j]].x<<" "<<v[st[j]].y<<endl;}
   // for(i=1;i<=j;i++)    g<<v[st[i]].x<<" "<<v[st[i]].y<<endl;// afisare 1/2 infasuratoare
   // for(i=1;i<=n;i++) g<<viz[i]<<" ";
  //  g<<endl;
  //g<<"====l"<<endl;

 for(i=n;i>=1;i--)
    if(viz[i]==0)
    {//g<<v[i].x<<"kk "<<v[i].y<<endl;
      while(viraj(v[st[j-1]],v[st[j]],v[i])<1&&j>1){//g<<viraj(v[st[j-1]],v[st[j]],v[i])<<endl;
      viz[st[j]]=0;j--;}//cat timp  punctul i se afla in dreapta sau coliniar
      j++;st[j]=i; viz[i]=1;
     // g<<v[st[j]].x<<" "<<v[st[j]].y<<endl;//
     // punctul se afla in stanga si fac viraj stanga
    } g.precision(6);

    for(i=1;i<=j;i++)   g<<v[st[i]].x<<" "<<v[st[i]].y<<endl;// afisare 1/2 infasuratoare
// for(i=1;i<=n;i++) g<<viz[i]<<" ";


     f.close();
     g.close();

    return 0;
}