Pagini recente » Cod sursa (job #585897) | Cod sursa (job #1402882) | Cod sursa (job #2485801) | Cod sursa (job #1971782) | Cod sursa (job #2090532)
#include<fstream>
#include<algorithm>
#include<vector>
#define MULT 1000000000
#define M 100000000
#define N 10000000
#define K 1000
#define EPS 1e-8
using namespace std;
ifstream cin("oypara.in");
ofstream cout("oypara.out");
class mazi{ ///segment
public:
int x,y1,y2;
mazi(int _x=0,int _y1=0,int _y2=0){
x=_x;
y1=_y1;
y2=_y2;
}
bool operator <(const mazi a) const{
if (x<a.x) return true;
if (x==a.x &&y1<a.y1) return true;
if (x==a.x &&y1==a.y1 &&y2<a.y2) return true;
return false;
}
};
vector<mazi> v;
int verif(double start,int x){
double st=-10*M,dr=+10*M;
for(int i=1;i<v.size();i++){
double a=(1.0*v[i].y1-start)/(1.0*v[i].x-x);
double b=(1.0*v[i].y2-start)/(1.0*v[i].x-x);
if (a>dr) return -1;
if (b<st) return 1;
if (a>st) st=a;
if (b<dr) dr=b;
}
return 0;
}
double panta(double start,int x){
double st=-10*M,dr=+10*M;
for(int i=1;i<v.size();i++){
double a=(1.0*v[i].y1-start)/(1.0*v[i].x-x);
double b=(1.0*v[i].y2-start)/(1.0*v[i].x-x);
if (a>st) st=a;
if (b<dr) dr=b;
}
if ((int)st!=(int)dr) return ((int)st+(int)dr+1)/2;
return (st+dr)/2;
}
int main(){
int n,i;
cin>>n;
for(i=1;i<=n;i++){
int a,b,c;
cin>>a>>b>>c;
v.push_back(mazi(a,b,c));
}
sort(v.begin(),v.end());
double st=v[0].y1,dr=v[0].y2;
double start=(st+dr)/2;
for(i=1;i<=K;i++){
int aux=verif(start,v[0].x);
if (verif((int)start,v[0].x)==0){
start=(int)start;
break;
}
if (aux<0) dr=start;
else st=start;
start=(st+dr)/2;
}
double a=panta(start,v[0].x);
double b=start-a*v[0].x;
double minsus=MULT;
int id=0;
for(i=0;i<v.size();i++){
double aux=a*v[i].x+b;
if (v[i].y2-aux<minsus &&v[i].y2>=1 &&v[i].y2<=M &&v[i].x>=1 &&v[i].x<=M){
minsus=v[i].y2-aux;
id=i;
}
}
b+=minsus;
cout<<v[id].x<<' '<<v[id].y2<<' ';
int ans=-1;
for(i=1;i<=N;i++){
if (v[id].x+i>M) break;
double aux=a*(v[id].x+i)+b;
if (aux-EPS<(int)aux &&(int)aux>=1 &&(int)aux<=M){
ans=(int)aux;
break;
}
/*if (aux+EPS>(int)aux+1 &&(int)aux+1>=1 &&(int)aux+1<=M){
ans=(int)aux+1;
break;
}*/
}
if (ans==-1){
for(i=-1;i>=-N;i--){
if (v[id].x+i<1) break;
double aux=a*(v[id].x+i)+b;
if (aux-EPS<(int)aux &&(int)aux>=1 &&(int)aux<=M){
ans=(int)aux;
break;
}
/*if (aux+EPS>(int)aux+1 &&(int)aux+1>=1 &&(int)aux+1<=M){
ans=(int)aux+1;
break;
}*/
}
}
cout<<v[id].x+i<<' '<<ans<<endl;
return 0;
}