Pagini recente » Cod sursa (job #913630) | Cod sursa (job #1120229) | Cod sursa (job #1725246) | Cod sursa (job #2467488) | Cod sursa (job #573166)
Cod sursa(job #573166)
using namespace std;
#include<fstream>
#include<algorithm>
struct punct{double x,y,panta;}v[120100],mx;
int ind[120100],st[120100],nr,vf;
bool cmp(punct a,punct b)
{return a.panta<b.panta;}
int verificare(int i)
{double a,b,c,d,e,f;
a=v[st[i-2]].y-v[st[i-1]].y;
b=v[st[i-2]].x-v[st[i-1]].x;
c=v[st[i]].y-v[st[i-1]].y;
d=v[st[i]].x-v[st[i-1]].x;
e=a/b;
f=c/d;
if(e<f)
return 0;
return 1;
/*a=v[st[i-2]].x-v[st[i-1]].x;
b=v[st[i-2]].y-v[st[i-1]].y;
c=(v[st[i]].x-v[st[i-1]].x)*b;
d=(v[st[i]].y-v[st[i-1]].y)*a;
c-=d;
if(c<=0)
return 0;
return 1;*/
}
inline void pop()
{st[--vf]=0;}
inline void push(int w)
{st[vf++]=w;}
int main()
{int n,i,j,k;
double a,b,r=-9999999;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
in>>n;
mx.x=mx.y=9999999;
for(i=0;i<n;i++)
{in>>v[i].x>>v[i].y;
if(v[i].x<mx.x||(v[i].x==mx.x&&v[i].y<mx.y))
{mx.x=v[i].x;
mx.y=v[i].y;
k=i;
}
}
in.close();
for(i=0;i<n;i++)
{a=mx.y-v[i].y;
b=mx.x-v[i].x;
if(b==0)
ind[nr++]=i;
else
{v[i].panta=a/b;
r=max(r,v[i].panta);
}
}
for(i=0;i<nr;i++)
v[ind[i]].panta=r+1;
v[k].panta=r+2;
sort(v,v+n,cmp);
push(n-1);
push(0);
for(i=1;i<n-1;i++)
{push(i);
while(!verificare(vf-1))
pop(),pop(),push(i);
}
out<<vf<<'\n';
j=n-1;
for(i=0;i<vf;i++)
out<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
out.close();
return 0;
}