Pagini recente » Cod sursa (job #2149005) | Cod sursa (job #76544) | Cod sursa (job #701027) | Cod sursa (job #1013277) | Cod sursa (job #3036374)
#include <bits/stdc++.h>
#define NMAX 120008
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
class Point {
private:
double x, y;
public:
friend istream& operator >>(istream& in, Point& p) {
in >> p.x >> p.y;
return in;
}
friend ostream& operator <<(ostream& out, const Point& p) {
out << fixed << setprecision(12) << p.x << ' ' << p.y;
return out;
}
friend bool operator < (const Point &a, const Point &b) {
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
friend Point operator - (const Point &a, const Point &b) {
Point ans;
ans.x = a.x - b.x;
ans.y = a.y - b.y;
return ans;
}
friend double operator * (const Point &a, const Point &b) {
return a.x * b.y - a.y * b.x;
}
};
vector <Point> Build(vector <Point> p) {
vector <Point> half;
for(auto A : p) {
while(half.size() >= 2) {
Point B = half[half.size() - 1];
Point C = half[half.size() - 2];
if((A - C) * (B - C) < 0) break;
half.pop_back();
}
half.push_back(A);
}
return half;
}
vector <Point> v;
int n;
int main() {
fin >> n;
for(int i = 1; i <= n; i ++) {
Point p; fin >> p;
v.push_back(p);
}
sort(v.begin(), v.end());
vector <Point> bot_half = Build(v);
// for(auto x : bot_half) fout << x << '\n';
// fout << "\n\n";
reverse(v.begin(), v.end());
vector <Point> top_half = Build(v);
// for(auto x : top_half) fout << x << '\n';
// fout << "\n\n";
reverse(bot_half.begin(), bot_half.end());
reverse(top_half.begin(), top_half.end());
bot_half.pop_back();
top_half.pop_back();
reverse(bot_half.begin(), bot_half.end());
reverse(top_half.begin(), top_half.end());
fout << top_half.size() + bot_half.size() << '\n';
for(auto x: bot_half) fout << x << '\n';
for(auto x: top_half) fout << x << '\n';
return 0;
}