Pagini recente » Cod sursa (job #2263124) | Cod sursa (job #1047546) | Cod sursa (job #3004967) | Cod sursa (job #964024) | Cod sursa (job #488084)
Cod sursa(job #488084)
#include<fstream>
using namespace std;
#define maxn 120001
#define inf 1000000000
double x[maxn],y[maxn];
long double v[maxn];
int pi,ind[maxn],st[maxn],n;
bool comf(int i,int j) //compar unghiul phi dintre 2 puncte cu orizontala...cu tangenta...
{
return (double)(x[i]-x[pi])*(y[j]-y[pi])<(double)(x[j]-x[pi])*(y[i]-y[pi]);
}
bool semn(int i,int j,int k)
{
return (x[i]*y[j]+x[j]*y[k]+x[k]*y[i]-y[i]*x[j]-y[j]*x[k]-y[k]*x[i])>0;
}
int main()
{
int pctinitial=0,i;
ifstream in("infasuratoare.in");
in>>n;
x[pctinitial]=y[pctinitial]=inf;
for(i=1;i<=n;i++)
{
in>>x[i]>>y[i];
if(x[i]<x[pctinitial]||(x[i]==x[pctinitial]&&y[i]<y[pctinitial]))
pctinitial=i;
}
pi=pctinitial;
for(i=1;i<=n;i++)
if(i!=pi)
ind[++ind[0]]=i;
sort(ind+1,ind+ind[0]+1,comf);
st[0]=1;
st[1]=pi;
for(i=1;i<n;i++)
{
while(st[0]>=2&&semn(st[st[0]-1],st[st[0]],ind[i])) st[0]--;
st[++st[0]]=ind[i];
}
st[++st[0]]=pi;
reverse(st+1,st+st[0]);
ofstream out("infasuratoare.out");
out<<st[0]-1<<'\n';
for(i=1;i<st[0];i++)
{
out<<x[st[i]]<<" "<<y[st[i]]<<'\n';
}
return 0;
}