Pagini recente » Cod sursa (job #1264592) | Cod sursa (job #1938231) | Cod sursa (job #2571106) | Cod sursa (job #2655992) | Cod sursa (job #3039449)
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const double PI = 3.14159265358979323846;
using point = pair<double, double>;
bool cmp(const point& a, const point& b) {
if (a == point{ 0, 0 }) return 1; if (b == point{ 0, 0 }) return 0;
if (a.first >= 0 && b.first >= 0) {
return a.second * b.first < b.second* a.first;
}
else if (a.first <= 0 && b.first >= 0) return 0;
else if (a.first >= 0 && b.first <= 0) return 1;
else {
return a.second * b.first < b.second* a.first;
}
}
int main() {
int n;
cin >> n;
vector<point> v;
point o = { -1, -1 };
for (int i = 1; i <= n; i++) {
double x, y;
cin >> x >> y;
v.push_back({ x, y });
if (o == point{-1, -1}) o = { x, y };
else if (o.second > y) {
o = { x, y };
}
else if (o.second == y && o.first > x) {
o = { x, y };
}
}
for (point& p : v) {
p.first -= o.first;
p.second -= o.second;
}
sort(v.begin(), v.end(), cmp);
cout << setprecision(6) << fixed;
//for (const point& p : v) {
// cout << p.first + o.first << ' ' << p.second + o.second << '\n';
//}
vector<int> s{};
s.push_back(0);
for (int i = 1; i < n; i++) {
if (s.size() < 2) {
s.push_back(i);
}
else {
while (s.size() >= 2) {
point p1 = v[s[s.size() - 2]];
point p2 = v[s[s.size() - 1]];
point p3 = v[i];
p1.first -= p2.first; p3.first -= p2.first;
p1.second -= p2.second; p3.second -= p2.second;
double a1;
if (p1.first == 0) {
if (p1.second > 0) a1 = PI / 2;
else if (p1.second < 0) a1 = 3 * PI / 2;
}
else a1 = atan(p1.second / p1.first) + (p1.first < 0 ? PI : 0);
double a3;
if (p3.first == 0) {
if (p3.second > 0) a3 = PI / 2;
else if (p3.second < 0) a3 = 3 * PI / 2;
}
else a3 = atan(p3.second / p3.first) + (p3.first < 0 ? PI : 0);
if (a1 - a3 + (a1 - a3 < 0 ? 2 * PI : 0) < PI) {
s.push_back(i);
break;
}
else s.pop_back();
}
}
}
cout << s.size() << '\n';
for (int i : s) {
cout << v[i].first + o.first << ' ' << v[i].second + o.second << '\n';
}
return 0;
}