Pagini recente » Cod sursa (job #1487262) | Cod sursa (job #767898) | Cod sursa (job #1824937) | Cod sursa (job #2711644) | Cod sursa (job #2876754)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int nmax=120005;
struct point
{
double x,y;
bool operator ^(const point & that)const
{
return x==that.x&&y==that.y;
}
bool operator <(const point &that) const
{
return make_pair(x,y)<make_pair(that.x,that.y);
}
};
point p0;
point p[nmax];
void minn(point &p1,point p2)
{
if(p2.y<p1.y)
p1=p2;
else
if(p2.x<p1.x&&p1.y==p2.y)
p1=p2;
}
int cw(point a,point b,point c)
{
double x=(b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);//-x
if(x>0)
return 1;
if(!x)
return x;
return -1;
}
int main()
{
int n;
int ind;
while(cin>>n&&n){
ind=1;
for(int i=1;i<=n;++i)
{
double a,b;
cin>>a>>b;
p[i].x=a;
p[i].y=b;
if(i==1)
p0=p[i];
point cop=p0;
p0=min(p0,p[i]);
if(!(cop^p0))
ind=i;
}
swap(p[1],p[ind]);
sort(p+2,p+n+1,[&p0](point a,point b)
{
int ori=cw(p0,a,b);
if(ori==0)
return (a.x-p0.x)*(a.x-p0.x)+(a.y -p0.y)*(a.y-p0.y)<=(b.x-p0.x)*(b.x-p0.x)+(b.y -p0.y)*(b.y-p0.y);
return ori>0;
});
int ans[nmax],vf=2;
int m=1;
/* for(int i=2;i<=n;++i)
{
while(i<n&&!cw(p0,p[i],p[i+1]))++i;
p[++m]=p[i];
}
n=m;*/
ans[1]=1;
ans[2]=2;
for(int i=3;i<=n;++i)
{
if((vf>1&&cw(p[ans[vf-1]],p[ans[vf]],p[i])!=1))
{
ans[vf]=i;
}
else
ans[++vf]=i;
}
int start=1;
if(vf==2)
{
if(!(p[1]^p[2]))
cout<<2<<'\n'<<p[1].x<<" "<<p[1].y<<'\n'<<p[2].x<<" "<<p[2].y;
else
cout<<1<<'\n'<<p[1].x<<" "<<p[1].y;
cout<<'\n';
break;
continue;
}
cout<<vf-start+1<<'\n';
for(;start<=vf;++start)
cout<<p[ans[start]].x<<" "<<p[ans[start]].y<<'\n';
break;
}
return 0;
}