Pagini recente » Cod sursa (job #177459) | Cod sursa (job #2760003) | Cod sursa (job #1906306) | Cod sursa (job #1894684) | Cod sursa (job #2836796)
#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 == 1)
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], pJ[j + 1], pS[i]) >= 0.0)
break;
if(det(pS[i], pS[i + 1], pJ[j]) <= 0.0){
fout << pS[i].x << ' ' << pS[i].y << ' ' << pJ[j].x << ' ' << pJ[j].y << '\n';
return 0;
}
}
return 0;
}