Cod sursa(job #1613689)

Utilizator GeanaVladGeana Vlad GeanaVlad Data 25 februarie 2016 16:14:10
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<iostream>
#include<fstream>
using namespace std;
 struct punct{int x,y;
		            };
punct a[120000];
int v[120000],st[120000],n,i,k,dir;

void modifica()
{ if(dir==1){i++;
             if(i==n) dir=-1;
             }
    else i--;
}
int semn(punct A,punct B,punct C)
{
    int p;
    p=(C.y-A.y)*(B.x-A.x)-(C.x-A.x)*(B.y-A.y);
    if(p<0)return -1;
           else return 1;
}
void acoperire()
{
    //Qsort((a,n);
dir=1;
st[1]=1;st[2]=2;v[1]=1;v[2]=1;
i=2;k=2;
while(i>1){
           modifica();
           if(i==0)break;
           while(k>1 && semn(a[st[k-1]],a[st[k]],a[i])==-1)
                                            {
                                             v[st[k]]=0;
                                             k--;
                                            }
            k++;
            st[k]=i;
            v[i]=1;
            }
}
void citeste()
{
  ifstream f("infasuratoare.in");
  f>>n;
  for(i=1;i<=n;i++)f>>a[i].x>>a[i].y;
  f.close();

}
int main()
{
citeste();
acoperire();
ofstream g("infasuratoare.out");
//for(i=1;i<=n;i++)cout<<v[i]<<' ';
g<<k;
for(i=1;i<=k;i++)g<<st[i]<<" ";
}