Pagini recente » Cod sursa (job #2718841) | Cod sursa (job #1227792) | Cod sursa (job #1903386) | Cod sursa (job #261208) | Cod sursa (job #2082432)
#include<fstream>
#include<algorithm>
#include<vector>
#define M 100000000
#define N 10000000
#define K 1000
#define EPS 1e-8
using namespace std;
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;
ifstream cin("oypara.in");
ofstream cout("oypara.out");
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;
int a1;
int b1=0;
for(a1=1;a1<=N;a1++){
double aux=a*a1+b;
if (aux-(int)aux<EPS &&(int)aux>=1 &&(int)aux<=M){
b1=(int)aux;
break;
}
if ((int)aux+1-aux<EPS &&(int)aux>=0 &&(int)aux<M){
b1=(int)aux+1;
break;
}
}
if (b1==0){
for(a1=10*M;a1>=10*M-N/2;a1--){
double aux=a*a1+b;
if (aux-(int)aux<EPS &&(int)aux>=1 &&(int)aux<=M){
b1=(int)aux;
break;
}
if ((int)aux+1-aux<EPS &&(int)aux>=0 &&(int)aux<M){
b1=(int)aux+1;
break;
}
}
}
cout<<a1<<' '<<b1<<' ';
int a2;
int b2=0;
for(a2=a1+1;a2<=N;a2++){
double aux=a*a2+b;
if (aux-(int)aux<EPS &&(int)aux>=1 &&(int)aux<=M){
b2=(int)aux;
break;
}
if ((int)aux+1-aux<EPS &&(int)aux>=0 &&(int)aux<M){
b2=(int)aux+1;
break;
}
}
if (b2==0){
if (a1<=10*M-N) a2=10*M;
else a2=a1-1;
for(;a2>=10*M-N/2;a2--){
double aux=a*a2+b;
if (aux-(int)aux<EPS &&(int)aux>=1 &&(int)aux<=M){
b2=(int)aux;
break;
}
if ((int)aux+1-aux<EPS &&(int)aux>=0 &&(int)aux<M){
b2=(int)aux+1;
break;
}
}
}
cout<<a2<<' '<<b2<<endl;
return 0;
}