Pagini recente » Cod sursa (job #2972645) | Cod sursa (job #3121465) | Cod sursa (job #1060921) | Cod sursa (job #983019) | Cod sursa (job #1608445)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
class Point {
public:
double x, y;
};
vector <Point> stk;
Point point[120005];
int point_nr;
void read() {
cin >> point_nr;
for(int i = 1; i <= point_nr; ++i) {
cin >> point[i].x >> point[i].y;
}
}
inline double cross_product(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
inline bool cmp(Point a, Point b) {
return cross_product(point[1], a, b) < 0;
}
void sort_point() {
int pos = 1;
for(int i = 2; i <= point_nr; ++i) {
if(point[i].x > point[pos].x) {
continue;
}
if(point[i].x < point[pos].x) {
pos = i;
continue;
}
if(point[i].y < point[pos].y) {
pos = i;
}
}
swap(point[1], point[pos]);
sort(&point[2], &point[point_nr + 1], cmp);
}
void solve() {
sort_point();
stk.push_back(point[1]);
stk.push_back(point[2]);
for(int i = 3; i <= point_nr; ++i) {
while(stk.size() >= 2 and cross_product(stk[stk.size() - 2], stk[stk.size() - 1], point[i]) > 0) {
stk.pop_back();
}
stk.push_back(point[i]);
}
}
void print() {
cout << fixed;
cout << stk.size() << '\n';
while(!stk.empty() ) {
cout << setprecision(13) << stk[stk.size() - 1].x << ' ' << stk[stk.size() - 1].y << '\n';
stk.pop_back();
}
}
int main() {
read();
solve();
print();
return 0;
}
/*
8
-14.000000 -6.000000
-12.000000 -11.000000
7.000000 -13.000000
12.000000 -1.000000
12.000000 1.000000
11.000000 7.000000
3.000000 11.000000
-8.000000 12.000000
*/