Pagini recente » Cod sursa (job #2570689) | Cod sursa (job #1759559) | Cod sursa (job #3283421) | Cod sursa (job #3247180) | Cod sursa (job #3221725)
/// la multi ani la arici <3
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree <long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update>
#define lsb(x)(x & (-x))
const long long max_size = 2e5 + 20;
pair <long long, long long> jos[max_size], sus[max_size];
long long n, k, t;
long long arie (pair <long long, long long> x, pair <long long, long long> y, pair <long long, long long> z)
{
return x.first * (y.second - z.second) + y.first * (z.second - x.second) + z.first * (x.second - y.second);
}
long long lowhull ()
{
vector <pair <long long, long long>> aux;
for (long long i = 1; i <= n; i++)
{
while (aux.size() > 1 && arie(aux[aux.size() - 2], aux.back(), sus[i]) <= 0)
{
aux.pop_back();
}
aux.push_back(sus[i]);
}
for (long long i = 0; i < aux.size(); i++)
{
sus[i + 1] = aux[i];
}
return aux.size();
}
long long uphull ()
{
vector <pair <long long, long long>> aux;
for (long long i = 1; i <= n; i++)
{
while (aux.size() > 1 && arie(aux[aux.size() - 2], aux.back(), jos[i]) >= 0)
{
aux.pop_back();
}
aux.push_back(jos[i]);
}
for (long long i = 0; i < aux.size(); i++)
{
jos[i + 1] = aux[i];
}
return aux.size();
}
bool check (pair <long long, long long> x, pair <long long, long long> y)
{
for (long long i = 1; i <= k; i++)
{
if (arie(x, y, sus[i]) < 0)
{
return 0;
}
}
for (long long i = 1; i <= t; i++)
{
if (arie(x, y, jos[i]) > 0)
{
return 0;
}
}
return 1;
}
void solve ()
{
cin >> n;
for (long long i = 1; i <= n; i++)
{
cin >> jos[i].first >> jos[i].second >> sus[i].second;
sus[i].first = jos[i].first;
}
sort(jos + 1, jos + n + 1);
sort(sus + 1, sus + n + 1);
k = lowhull(), t = uphull();
long long i = 1, j = 1;
while (i < k && j <= t)
{
while (j <= t && arie(sus[i], sus[i + 1], jos[j]) <= 0)
{
j++;
}
i++;
}
if (i < k && check(sus[i], sus[i + 1]))
{
cout << sus[i].first << " " << sus[i].second << " " << sus[i + 1].first << " " << sus[i + 1].second;
return;
}
i = 1, j = 1;
while (i <= k && j < t)
{
while (i <= k && arie(jos[j], jos[j + 1], sus[i]) >= 0)
{
i++;
}
j++;
}
if (j < t && check(jos[j], jos[j + 1]))
{
cout << jos[j].first << " " << jos[j].second << " " << jos[j + 1].first << " " << jos[j + 1].second;
}
cout << '\n';
}
signed main ()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#else
freopen("oypara.in", "r", stdin);
freopen("oypara.out", "w", stdout);
#endif // LOCAL
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
long long tt;
//cin >> tt;
tt = 1;
while (tt--)
{
solve();
}
return 0;
}