Pagini recente » Cod sursa (job #3238260) | Cod sursa (job #2303202) | Cod sursa (job #2935597) | Cod sursa (job #2438109) | Cod sursa (job #881816)
Cod sursa(job #881816)
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#define eps 1.e-12
#define inf 1.e9
using namespace std;
struct MyStruct {double x,y;} a;
vector<MyStruct> v;
inline double cp(const MyStruct &p1,const MyStruct &p2,const MyStruct &p3)
{
return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
int st[120005];
class MyComp
{
public:
inline bool operator()(const MyStruct &p,const MyStruct &q)
{
return cp(a,p,q)<-eps;
}
};
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i,ind,top=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&a.x,&a.y),v.push_back(a);
a=v[0];ind=0;
for(i=1;i<(int)v.size();i++)
if(v[i].x-a.x<-eps)
ind=i,a=v[i];
else
if(fabs(v[i].x-a.x)<eps && v[i].y-a.y<-eps)
ind=i,a=v[i];
v.erase(v.begin()+ind);
sort(v.begin(),v.end(),MyComp());
v.push_back(a);
st[++top]=v.size()-1;st[++top]=0;
for(i=1;i<(int)v.size()-1;i++)
{
while(top>=2 && cp(v[st[top-1]],v[st[top]],v[i])>eps) {st[top]=0;top--;}
st[++top]=i;
}
printf("%d\n",top);
for(i=top;i>=1;i--)
printf("%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
return 0;
}