Pagini recente » Cod sursa (job #1011947) | Cod sursa (job #1397712) | Cod sursa (job #397122) | Cod sursa (job #2675533) | Cod sursa (job #1608024)
#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 = 1; i <= point_nr; ++i) {
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() - 1], stk[stk.size() - 2], 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;
}