Pagini recente » Cod sursa (job #508565) | Cod sursa (job #1425579) | Cod sursa (job #708817) | Cod sursa (job #2208627) | Cod sursa (job #2882210)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define NMax 120
#define CMax 1200000
#define Point pair<double,double>
#define mp make_pair
Point S = mp(CMax, CMax);
bool comparator(const Point& p1, const Point& p2) {
double x1, y1, x2, y2, x3, y3;
x1 = S.first; y1 = S.second;
x2 = p1.first; y2 = p1.second;
x3 = p2.first; y3 = p2.second;
return (y2 - y1) * (x3 - x1) - (y3 - y1) * (x2 - x1) >= 1e-12;
}
bool ccw(Point &p1, Point &p2, Point &p3) {
double x1, y1, x2, y2, x3, y3;
x1 = p1.first; y1 = p1.second;
x2 = p2.first; y2 = p2.second;
x3 = p3.first; y3 = p3.second;
return (y2 - y1) * (x3 - x1) - (y3 - y1) * (x2 - x1) < 1e-12;
}
int N;
vector<Point> points;
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &N);
int index = -1;
points.push_back(mp(CMax,CMax));
for(int i = 1; i <= N; i++) {
double x, y;
scanf("%lf %lf", &x, &y);
points.push_back(mp(x, y));
if(y < S.second) {
S = mp(x, y);
index = i;
}
else if(abs(y - S.second) < 1e-12) {
if(x < S.first) {
S = mp(x, y);
index = i;
}
}
}
swap(points[1], points[index]);
sort(points.begin() + 2, points.end(), comparator);
Point st[N + 2];
st[1] = points[1];
st[2] = points[2];
int k = 2;
for(int i = 3; i <= N; i++) {
k++;
st[k] = points[i];
while(k >= 3 && ccw(st[k - 2], st[k - 1], st[k])) {
st[k - 1] = st[k];
k--;
}
}
printf("%d\n", k);
printf("%lf %lf\n", S.first, S.second);
for(int i = k; i >= 2; i--) {
printf("%lf %lf\n", st[i].first, st[i].second);
}
return 0;
}