Pagini recente » Cod sursa (job #2036170) | Cod sursa (job #3316323) | Cod sursa (job #324578) | Cod sursa (job #1697875) | Cod sursa (job #3315954)
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int MXN = 120000;
const int BRD = 1e9;
int n;
double x, y;
pair<double, double> v[MXN + 1],
sus[MXN + 1],
jos[MXN + 1];
int vf, vf1, vf2;
bool cmp(pair<double, double> A, pair<double, double> B) {
if(A.f != B.f)
return A.f < B.f;
else
return A.s < B.s;
}
bool peste(pair<double, double> A, pair<double, double> B, pair<double, double> C) {
// "+" -> peste
// "-" -> sub
return (A.f * B.s + B.f * C.s + C.f * A.s > C.f * B.s + A.f * C.s + B.f * A.s);
}
int main()
{
cin >> n;
vf = 0;
for(int i = 1; i <= n; ++i) {
cin >> x >> y;
//x += BRD, y += BRD;
v[++vf].f = x, v[vf].s = y;
}
sort(v + 1, v + 1 + n);
pair <double, double> a1 = v[1], a2 = v[n];
vf1 = vf2 = 0;
for(int i = 2; i < n; ++i) {
if(peste(a1, a2, v[i]))
sus[++vf1] = v[i];
else
jos[++vf2] = v[i];
}
stack <int> st;
st.push(1), st.push(2);
pair <double, double> p1, p2;
int u1, u2;
for(int i = 3; i <= vf1; ++i) {
u2 = st.top(), st.pop();
u1 = st.top(), st.push(u2);
p1 = v[u1], p2 = v[u2];
cout << p1.f << ' ' << p1.s << '\n';
cout << p2.f << ' ' << p2.s << '\n';
if(peste(p1, p2, sus[i]))
st.push(i);
else
st.pop(), st.push(i);
}
cout << '\n';
int sz1, sz2;
sz1 = st.size();
while(!st.empty())
st.pop();
st.push(1), st.push(2);
for(int i = 3; i <= vf2; ++i) {
u2 = st.top(), st.pop();
u1 = st.top(), st.push(u2);
p1 = v[u1], p2 = v[u2];
cout << p1.f << ' ' << p1.s << '\n';
cout << p2.f << ' ' << p2.s << '\n';
if(!peste(p1, p2, sus[i]))
st.push(i);
else
st.pop(), st.push(i);
}
sz2 = st.size();
return 0;
}