Pagini recente » Cod sursa (job #1838079) | Cod sursa (job #676795) | Cod sursa (job #196943) | Cod sursa (job #2947538) | Cod sursa (job #573184)
Cod sursa(job #573184)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
struct punct{double x,y,panta;}v[120100],mx;
int ind[120100],st[120100],nr,vf;
bool cmp(punct a,punct b)
{if (a.panta==b.panta)
return a.x<b.x;
return a.panta<b.panta;}
int verificare(int i)
{double a,b,c,d;
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;
/*long long x;
x=v[st[a]].x*(v[st[b]].y-v[st[c]].y)+v[st[b]].x*
(v[st[c]].y-v[st[a]].y)+v[st[c]].x*(v[st[a]].y-v[st[b]].y);
if(x>0)
return 1;
return 0;*/
}
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<<setprecision(12)<<v[st[i]].x<<" "<<setprecision(12)<<v[st[i]].y<<'\n';
out.close();
return 0;
}