Pagini recente » Cod sursa (job #1295433) | Cod sursa (job #1386520) | Cod sursa (job #1646181) | Cod sursa (job #27567) | Cod sursa (job #2836658)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("oypara.in");
ofstream fout("oypara.out");
const int NMAX(100005);
struct chestie
{
int x, y;
} sus[NMAX], jos[NMAX], pJ[NMAX], pS[NMAX], care;
int n, cnt[3];
double det(chestie a, chestie b, chestie c)
{
return ((a.x * b.y + a.y * c.x + b.x * c.y) - (b.y * c.x + a.y * b.x + a.x * c.y));
}
inline bool cmp1(chestie a, chestie b)
{
if(a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
inline bool cmp2(chestie a, chestie b)
{
return (det(care, a, b) > 0.0);
}
inline void solve(chestie vec[], chestie st[], int ind)
{
sort(vec + 1, vec + n + 1, cmp1);
if(ind == 0)
reverse(vec + 1, vec + n + 1);
care = vec[1];
sort(vec + 2, vec + n + 1, cmp2);
st[++cnt[ind]] = vec[1];
st[++cnt[ind]] = vec[2];
for(int i = 3; i <= n + 1; ++i)
{
while(cnt[ind] >= 2 && det(st[cnt[ind] - 1], st[cnt[ind]], vec[i]) <= 0.0)
--cnt[ind];
st[++cnt[ind]] = vec[i];
}
}
int main()
{
fin >> n;
for(int i = 1; i <= n; ++i)
{
int x, y1, y2;
fin >> x >> y1 >> y2;
jos[i] = {x, y1};
sus[i] = {x, y2};
}
solve(jos, pJ, 0);
solve(sus, pS, 1);
int i = 1;
for(int j = 1; j <= cnt[0]; ++j)
{
for(; i < cnt[1]; ++i)
if(det(pJ[j], pS[i], pS[i + 1]) >= 0.0)
break;
int nxt = j + 1;
if(nxt == cnt[0] + 1)
nxt = 1;
if(det(pJ[j], pS[i], pJ[nxt]) <= 0.0){
fout << pS[i].x << ' ' << pS[i].y << ' ' << pJ[j].x << ' ' << pJ[j].y << '\n';
return 0;
}
}
return 0;
}