Pagini recente » Cod sursa (job #1864621) | Cod sursa (job #990869) | Cod sursa (job #860628) | Cod sursa (job #843864) | Cod sursa (job #1569099)
#include <cstdio>
#include <algorithm>
FILE* in=fopen("oypara.in","r");
FILE* out=fopen("oypara.out","w");
const int Q=100007;
struct point{
int x,y;
} a[Q], b[Q];
int buna[Q],super[Q];
bool cmp(const point &f, const point &g)
{
return f.x<g.x;
}
int clock(const point &u,const point &f, const point &g)
{
if((f.x-u.x)*(g.y-u.y)-(f.y-u.y)*(g.x-u.x) > 0)
return 1;
if((f.x-u.x)*(g.y-u.y)-(f.y-u.y)*(g.x-u.x) < 0)
return -1;
return 0;
}
int n;
void finise(point a, point b)
{
fprintf(out,"%d %d %d %d",a.x,a.y,b.x,b.y);
}
int main()
{
fscanf(in,"%d",&n);
int x,y1,y2;
int min=1;
for(int i=1; i<=n; i++)
{
fscanf(in,"%d%d%d",&x,&y1,&y2);
a[i].x=x;
a[i].y=y1;
b[i].x=x;
b[i].y=y2;
}
std::sort(a+1,a+n,cmp);
std::sort(b+1,b+n,cmp);
buna[0]=2;
buna[1]=1;
buna[2]=2;
super[0]=2;
super[1]=1;
super[2]=2;
for(int i=3; i<=n; i++)
{
while(buna[0]>=2 && clock(a[buna[buna[0]-1]], a[buna[buna[0]] ], a[i]) !=-1)
buna[0]--;
buna[++buna[0]]=i;
while(super[0]>=2 && clock(b[super[super[0]-1]],b[super[super[0]]],b[i])!=1)
super[0]--;
super[++super[0]]=i;
}
int A=1, B=1;
while(A<buna[0] && B<super[0])
{
if(clock(a[buna[A]],b[super[B]],b[super[B+1]])!=-1)
{
finise(a[buna[A]],b[super[B]]);
return 0;
}
if(clock(a[buna[A]],a[buna[A+1]],b[super[B+1]])==-1)
{
A++;
}
else if(clock(b[super[B]],b[super[B]+1],a[buna[A+1]]))
{
B++;
}
}
finise(a[buna[A]],b[super[B]]);
return 0;
}