Pagini recente » Cod sursa (job #1722447) | Cod sursa (job #2589469) | Cod sursa (job #52423) | Cod sursa (job #386854) | Cod sursa (job #1613689)
#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]<<" ";
}