Pagini recente » Cod sursa (job #2923580) | Cod sursa (job #917571) | Cod sursa (job #1286808) | Cod sursa (job #2532833) | Cod sursa (job #2477893)
#include <bits/stdc++.h>
using namespace std;
pair <float, float> bottom_point;
int orient(pair<float, float> p1, pair<float, float> p2, pair<float, float> p3) {
int s = p1.first * p2.second + p2.first * p3.second + p3.first * p1.second - p3.first * p2.second - p1.first * p3.second - p2.first * p1.second;
if (s == 0) {
return 0;
}
if (s < 0) {
return 1;
}
return 2;
}
int dist(pair<int, int> p1, pair <int, int> p2)
{
return (p1.first - p2.first)*(p1.first - p2.first) +
(p1.second - p2.second)*(p1.second - p2.second);
}
bool cmp(pair<float, float> p1, pair<float, float> p2) {
int o = orient(bottom_point, p1, p2);
if (o == 0) {
return (dist(bottom_point, p1) >= dist(bottom_point, p2) ) ? -1:1;
}
return (o == 2)? -1:1;
}
int main()
{
vector< pair<float, float> > hull;
vector< pair<float, float> > points;
cin >> bottom_point.first >> bottom_point.second;
points.push_back(bottom_point);
for (int i = 0; i < 3; i++) {
pair <float, float> p;
cin >> p.first >> p.second;
points.push_back(p);
if (p.second < bottom_point.second) {
bottom_point = p;
} else if (p.second == bottom_point.second && p.first < bottom_point.first) {
bottom_point = p;
}
}
int pos = -1;
bool ok = true;
for (pair <float, float> it : points) {
pos ++;
if (it == bottom_point) {
pair<float, float> aux;
aux = points[pos];
points[pos] = points[0];
points[0] = aux;
ok = false;
}
}
sort(points.begin() + 1, points.end(), cmp());
stack <pair<float, float>> st;
st.push(points[0]);
st.push(points[1]);
for (int i = 2; i < 3; i++) {
while (st.size() >= 2 && orient(st[st.size() - 2], st[st.size() - 1], points[i])) {
st.pop();
}
st.push(points[i])
}
vector <pair <float, float> > points1;
for (pair<int, int> it : points) {
bool ok = true;
for (pair<float, float> it1 : st) {
if (it1 == it) {
ok = false;
}
}
if (ok) {
points1.push_back(it);
}
}
if (st.size() == 2) {
cout << st[0].first << " " << st[0].second << " si " << points1[0].first << " " << points1[0].second << endl;
cout << st[1].first << " " << st[1].second << " si " << points1[1].first << " " << points1[1].second << endl;
}
else if(st.size() == 3) {
cout << st[0].first << " " << st[0].second << " ";
cout << st[1].first << " " << st[1].second << " ";
cout << st[2].first << " " << st[2].second << endl;
cout << points1[0].first << " " << points1[0].second;
} else {
for (pair<float, float> it : st) {
cout << it.first << " " << it.second << endl;
}
}
return 0;
}