Pagini recente » Cod sursa (job #101168) | Cod sursa (job #500664) | Cod sursa (job #826265) | Cod sursa (job #1859190) | Cod sursa (job #2259914)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,j,k,nsv,x1,x2;
struct punct
{
int x,y;
double up;
};
punct v[105],st[105],sv;
int cmp(punct A,punct B)
{
if(A.up==B.up)
if(A.y==B.y)
return A.x<B.x;
else
return A.y<B.y;
return A.up<B.up;
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>v[i].x>>v[i].y;
if(i==1)
{
sv.x=v[i].x;
sv.y=v[i].y;
sv.up=0;
nsv=i;
}
else
if(v[i].y<sv.y||(v[i].y==sv.y&&v[i].x<sv.x))
{ sv.x=v[i].x;
sv.y=v[i].y;
sv.up=0;
nsv=i;
}
}
for(j=1;j<=n;j++)
if(j!=nsv)
{
v[j].up=(v[j].x-sv.x)/sqrt((v[j].x-sv.x)*(v[j].x-sv.x)+(v[j].y-sv.y)*(v[j].y-sv.y));
v[j].up=acos(v[j].up);
}
sort(v+1,v+n+1,cmp);
st[1].x=v[1].x;
st[1].y=v[1].y;
st[2].x=v[2].x;
st[2].y=v[2].y;
k=2;
if(n>=3)
{
st[3].x=v[3].x;
st[3].y=v[3].y;
j=3;
k=3;
while(j<n)
{if(st[k-2].x*st[k-2].y+st[k-1].x*st[k].y+st[k].x*st[k-2].y-st[k].x*st[k-1].y-st[k-2].x*st[k].y-st[k-1].x*st[k-2].y>=0)
{j++;
k++;
st[k]=v[j];}
else
{
st[k-1]=st[k];
k--;
}
if(st[k-2].x*st[k-2].y+st[k-1].x*st[k].y+st[k].x*st[k-2].y-st[k].x*st[k-1].y-st[k-2].x*st[k].y-st[k-1].x*st[k-2].y<0)
{
st[k-1].x=st[k].x;
st[k-1].y=st[k].y;
k--;
}
}
x1=st[k].x;
x2=st[k].y;
for(i=n;i>=1&&v[i].up==st[k].up;i--)
if(v[i].x!=x1||v[i].y!=x2)
{
k++;
st[k]=v[i];
}
g<<k<<"\n";
for(j=1;j<=k;j++)
g<<st[j].x<<" "<<st[j].y<<"\n";
}
return 0;
}