Pagini recente » Cod sursa (job #2321672) | Cod sursa (job #1043490) | Cod sursa (job #1595237) | Cod sursa (job #670041) | Cod sursa (job #2884022)
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
//ifstream cin("infasuratoareconvexa.in");
//ofstream cout("infasuratoareconvexa.out");
int h[1205];
const double eps = 1.0e-14;
const double INF = 1e9;
struct POINT
{
double x, y;
};
POINT ll;
POINT v[1205];
double dis(POINT P1, POINT P2)
{
return sqrt((P1.x - P2.x) * (P1.x - P2.x) + (P1.y - P2.y) * (P1.y - P2.y));
}
double cp(POINT P1, POINT P2, POINT P3)
{
return (P2.x - P1.x) * (P3.y - P2.y) - (P2.y - P1.y) * (P3.x - P2.x);
}
int ccw(POINT P1, POINT P2, POINT P3)
{
double k = cp(P1, P2, P3);
if(fabs(k) < eps)
return 0;
if(k >= eps)
return 1;
return -1;
}
bool cmp(POINT P1, POINT P2)
{
if(ccw(ll, P1, P2) == 0)
return dis(ll, P1) < dis(ll, P2);
return ccw(ll, P1, P2) > 0;
}
int main()
{
int n, i;
cin >> n;
cin >> v[0].x >> v[0].y;
for(i = 1; i < n; i++){
cin >> v[i].x >> v[i].y;
if(v[i].y - v[0].y <= -eps or (fabs(v[i].y - v[0].y) < eps and v[i].x - v[0].x <= -eps))
swap(v[0], v[i]);
}
ll = v[0];
sort(v + 1, v + n, cmp);
h[0] = 0;
h[1] = 1;
v[n] = v[0];
int top = 1;
i = 2;
while(i <= n){
if(ccw(v[h[top - 1]], v[h[top]], v[i]) >= 0){
h[++top] = i;
i++;
}
else
top--;
}
cout << top << "\n";
for(i = 0; i < top; i++)
cout << v[h[i]].x << " " << v[h[i]].y << "\n";
return 0;
}