Pagini recente » Cod sursa (job #2829997) | Cod sursa (job #1216937) | Cod sursa (job #142833) | Cod sursa (job #784933) | Cod sursa (job #2753926)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 120000;
const double eps = 1.0e-14;
const double INF = 1e9;
struct POINT
{
double x, y;
};
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
POINT ll;
POINT v[NMAX + 5];
int h[NMAX + 5];
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)
{
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 << fixed << setprecision(6) << v[h[i]].x << " " << v[h[i]].y << "\n";
cout << "\n";
return 0;
}