Pagini recente » Cod sursa (job #1749053) | Cod sursa (job #2728122) | Cod sursa (job #1098523) | Cod sursa (job #1579815) | Cod sursa (job #1109039)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream F("oypara.in");
ofstream G("oypara.out");
const int N = 100010;
typedef pair<int,int> pii;
#define x first
#define y second
#define y1 second.first
#define y2 second.second
vector< pair<int,pii> > lines;
vector<pii> up,down;
bool ecu(pii A,pii B,pii C)
{
int a = A.y - B.y;
int b = B.x - A.x;
long long c = - B.x * A.y + A.x * B.y;
return ( 1LL * a * C.x + 1LL * b * C.y + c ) > 0;
}
vector<pii> parc(vector<pii> a,int l,int r)
{
int step = l < r ? 1 : -1;
vector<pii> out;
for (int i=l;i!=(r+step);i+=step)
if ( i == l || i == r || ecu(a[l],a[r],a[i]) == 1 )
{
out.push_back(a[i]);
if ( out.size() > 2 )
while ( ecu(out[int(out.size())-3],out[int(out.size())-1],out[int(out.size())-2]) == -1 )
{
out[int(out.size())-2] = out[int(out.size())-1];
out.pop_back();
if ( out.size() <= 2 ) break;
}
}
return out;
}
vector<pii> convex_hull(vector<pii> a)
{
sort(a.begin(),a.end());
vector<pii> out,stack;
int n = a.size();
stack = parc(a,0,n-1);
for (int i=0;i<int(stack.size())-1;++i)
out.push_back(stack[i]);
stack = parc(a,n-1,0);
for (int i=0;i<int(stack.size())-1;++i)
out.push_back(stack[i]);
reverse(out.begin(),out.end());
return out;
}
bool solve()
{
int where = 0;
for (int i=0;i<int(down.size());++i)
{
// mut in fata
while ( 1 )
{
int next = ( where == int(up.size())-1 ) ? 0 : where+1;
if ( ecu(down[i],up[where],up[next]) <= 0 )
break;
where = next;
}
// mut in spate
while ( 1 )
{
int last = ( where == 0 ) ? int(up.size())-1 : where-1;
if ( ecu(down[i],up[where],up[last]) <= 0 )
break;
where = last;
}
int next = ( i == int(down.size())-1 ) ? 0 : i+1;
int last = ( i == 0 ) ? int(down.size())-1 : i-1;
if ( ecu( down[i],up[where],down[next] ) >= 0 && ecu( down[i],up[where],down[last] ) >= 0 )
// ambele sunt sub el atunci am solutie
{
G<<down[i].x<<' '<<down[i].y<<' ';
G<<up[where].x<<' '<<up[where].y<<'\n';
return 1;
}
}
return 0;
}
int main()
{
int n = 0;
F>>n;
for (int i=1;i<=n;++i)
{
pair<int,pii> pt;
F>>pt.x>>pt.y1>>pt.y2;
lines.push_back( pt );
}
sort(lines.begin(),lines.end());
for (int i=0;i<n;++i)
{
up.push_back( make_pair(lines[i].x,lines[i].y2) );
down.push_back( make_pair(lines[i].x,lines[i].y1) );
}
up = convex_hull(up);
down = convex_hull(down);
if ( !solve() )
{
swap(up,down);
solve();
}
}