Pagini recente » Cod sursa (job #849001) | Cod sursa (job #2770443) | Cod sursa (job #607405) | Cod sursa (job #389296) | Cod sursa (job #1149578)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("oypara.in");
ofstream fout ("oypara.out");
struct punct {
int x;
int y;
}s[100010],j[100010],pct,S,J;
int arie (punct i, punct j, punct k) {
double ariec = (j.x-i.x)*(k.y-i.y)-(k.x-i.x)*(j.y-i.y);
if (ariec<=0.0001)
return 1;
else
return 0;
}
int cmp (punct a, punct b) {
return arie(pct,a,b);
}
int n,x,y1,y2,i,i1[100010],i2[100010],minimj,minims,iminj,imins,aux1,aux2,p,p1,p2,e,k;
int main () {
fin>>n;
for (i=1;i<=n;i++) {
fin>>x>>y1>>y2;
j[i].x=s[i].x=x;
j[i].y=y1;
s[i].y=y2;
if (x<minimj) {
minimj=x;
iminj=i;
}else
if (x==minimj&& y1<j[iminj].y)
iminj=i;
if (x<minims) {
minims=x;
imins=i;
}else
if (x==minims&& y2<s[imins].y)
imins=i;
}
aux1=j[1].x;aux2=j[1].y;
j[1].x=j[iminj].x;j[1].y=j[iminj].y;
j[iminj].x=aux1;j[iminj].y=aux2;
pct=j[1];
sort (j+2,j+n+1,cmp);
i1[1]=n;
i1[2]=n-1;
p=2;
for (i=n-2;i>=1;i--) {
while( arie (j[i1[p-1]],j[i1[p]],j[i]) && p>=1 )
p--;
i1[++p]=i;
}
i1[++p]=i1[1];
p1=p;
aux1=s[1].x; aux2=s[1].y;
s[1].x=s[iminj].x; s[1].y=j[iminj].y;
s[iminj].x=aux1; s[iminj].y=aux2;
pct=s[1];
sort (s+2,s+n+1,cmp);
i2[1]=n;
i2[2]=n-1;
p=2;
for (i=n-2;i>=1;i--) {
while( arie (s[i2[p-1]],s[i2[p]],j[i]) && p>=1 )
p--;
i2[++p]=i;
}
i2[++p]=i2[1];
p2=p;
for (i=1,k=1;i<p2;i++) {
for (;arie(s[i2[i]], s[i2[i+1]],j[i1[k]])&&k<=p1;k++);
if (k>=p1) {
S=s[i2[i]];
break;
}
}
for (i=1;i<p1;i++)
if (arie(j[i1[i]],j[i2[i+1]],S)) {
J=j[i1[i]];
break;
}
fout<<S.x<<" "<<S.y<<" "<<J.x<<" "<<J.y<<"\n";
return 0;
}