Pagini recente » Cod sursa (job #75915) | Cod sursa (job #701125) | Cod sursa (job #2602088) | Cod sursa (job #2702710) | Cod sursa (job #3235453)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <cmath>
#define INF 99999999999.0
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct pct {
double x, y;
double cos;
};
vector<pct> v;
pct jos;
void read() {
int N;
jos.x = INF;
jos.y = INF;
jos.cos = 0;
fin >> N;
v.resize(N);
for (int i = 0; i < N; ++i) {
fin >> v[i].x >> v[i].y;
if (jos.y > v[i].y) {
jos = v[i];
}
else if (jos.y == v[i].y){
if (jos.x < v[i].x) {
jos = v[i];
}
}
}
}
double calc_cos(pct a, pct b) {
if (a.x == b.x && a.y == b.y) {
return INF;
}
return (b.x - a.x) / sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}
void complete_cos() {
for (auto & i : v) {
i.cos = calc_cos(i, jos);
}
}
bool comp(pct a, pct b) {
return a.cos < b.cos;
}
double dist(pct a, pct b) {
return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}
double cross_product(pct a, pct b, pct c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
pct second_to_top(stack<pct> &s) {
pct tp = s.top();
s.pop();
pct tp2 = s.top();
s.push(tp);
return tp2;
}
int main() {
read();
complete_cos();
sort(v.begin(), v.end(), comp);
stack<pct> st;
vector<pct> puncte;
for (auto &punct : v) {
if (!puncte.empty() && puncte.back().cos == punct.cos) {
if (dist(jos, punct) > dist(jos, puncte.back())) {
puncte.pop_back();
}
}
puncte.push_back(punct);
}
for (auto &punct : puncte) {
while (st.size() >= 2 && cross_product(second_to_top(st), st.top(), punct) <= 0) {
st.pop();
}
st.push(punct);
}
vector<pct> ans;
while (!st.empty()) {
ans.push_back(st.top());
st.pop();
}
reverse(ans.begin(), ans.end());
fout << ans.size() << "\n";
for (auto& p : ans) {
fout << fixed << setprecision(6) << p.x << " " << p.y << "\n";
}
return 0;
}