Pagini recente » Cod sursa (job #1557797) | Cod sursa (job #1274119) | Cod sursa (job #313020) | Cod sursa (job #2052877) | Cod sursa (job #2080896)
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1.e-14;
struct point{
double x,y;
};
point ll;
double cp(point p1,point p2,point p3)
{
return (p3.x-p1.x)*(p3.y-p2.y)
- (p3.y - p1.y) * (p3.x - p2.x );
}
int ccw(point p1,point p2,point p3)
{
double c =cp(p1,p2,p3);
if(fabs(c)<eps)
return 0;
if(c > eps)
return 1;
return -1;
}
double dist (point p1 , point p2)
{
return sqrt((p1.x-p2.x)*(p1.x- p2.x) + (p1.y-p2.y)*(p1.y- p2.y));
}
vector <point>v;
int st[120001];
bool cmp(point a,point b)
{
return ccw(v[0], a, b) > ccw(v[0], b, a);
}
int main(){
int n,i,poz,top;
double x,y;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
ll.x=1000000005;
ll.y=1000000005;
for(i = 1; i <= n ; i ++)
{
scanf("%lf%lf",&x,&y);
v.push_back({x,y});
if(ll.y - y >= eps){
ll.y = y;
ll.x = x;
poz=i;
}
else if(fabs(ll.y - y) <= eps)
if(ll.x - x >= eps)
{
ll.y = y;
ll.x = x;
poz=i;
}
}
swap(v[0],v[poz]);
sort(v.begin() + 1, v.begin() + n, cmp);
st[0] = 0;
st[1] = 1;
top = 1;
v[n] = v[0];
for (int i = 2; i <= n; ++i){
while (top > 1 && ccw(v[st[top]], v[st[top - 1]], v[i]) != ccw(v[st[top]], v[st[top - 1]], v[st[top - 2]]))
top--;
st[++top] = i;
}
printf("%d\n",top);
for(i = 0; i < top ;i ++)
printf("%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
return 0;
}