Submission #35198

---

Source Code Expand

#include<cmath>
#include<algorithm>
#include"ghost.h"
#include"grader.h"

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const double EPS=1e-11;

template<class T>
struct point{
	T x,y,z;
	point operator+(const point &a)const{ return (point){x+a.x,y+a.y}; }
	point operator-(const point &a)const{ return (point){x-a.x,y-a.y}; }
};

template<class T>
point<T> operator*(T c,const point<T> &a){ return (point<T>){c*a.x,c*a.y}; }

bool cmp_yz(const point<double> &a,const point<double> &b){
	return a.y+EPS<b.y || abs(a.y-b.y)<EPS && a.z+EPS<b.z;
}

template<class T>
T cross(const point<T> &a,const point<T> &b){ return a.x*b.y-a.y*b.x; }

template<class T>
struct line{ point<T> a,b; };

template<class T>
point<double> get_intersect(const line<T> &L1,const line<T> &L2){
	double a1=cross(L1.b-L1.a,L2.b-L2.a);
	double a2=cross(L1.b-L1.a,L1.b-L2.a);
	if(a1==0) return L1.a; // L1 == L2
	return (point<double>)L2.a+a2/a1*(point<double>)(L2.b-L2.a);
}

double dist_xz(const point<double> &a,const point<double> &b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.z-b.z)*(a.z-b.z));
}

double f(int n,const point<double> *C,const point<double> *T,const point<double> &G){
	double dif=0;
	rep(i,n){
		dif+=abs(T[i].z-(C[i].z+dist_xz(C[i],T[i])/dist_xz(C[i],G)*(G.z-C[i].z)));
	}
	return dif;
}

void FindGhost(int n,double Cx[],double Cy[],double Cz[],double Ty[],double Tz[]){
	// まず z=0 の平面で考える
	static point<double> C[100000],T[100000]; // candle, target
	rep(i,n){
		C[i]=(point<double>){Cx[i],Cy[i],Cz[i]};
		T[i]=(point<double>){0,Ty[i],Tz[i]};
	}

	sort(T,T+n,cmp_yz);

	const line<double> L={(point<double>){1,0},(point<double>){1,1}}; // 直線 x=1
	double y_min=77,y_max=-77;
	rep(i,n){
		y_min=min(y_min,get_intersect((line<double>){C[i],T[n-1]},L).y);
		y_max=max(y_max,get_intersect((line<double>){C[i],T[ 0 ]},L).y);
	}

	// 平面 z=0 に射影したおばけの位置
	point<double> G=get_intersect((line<double>){(point<double>){1,y_min},T[n-1]},
								  (line<double>){(point<double>){1,y_max},T[ 0 ]});

	// ろうそくたちを <ろうそくとおばけを結ぶ線分と直線 x=1 の交点の y　座標, ろうそくの z 座標> の辞書順でソート
	static pair<pair<double,double>,int> Y[100000];
	rep(i,n){
		Y[i]=make_pair(make_pair(get_intersect((line<double>){C[i],G},L).y,C[i].z),i);
	}
	sort(Y,Y+n);
	static point<double> tmp[100000];
	rep(i,n) tmp[i]=C[i];
	rep(i,n) C[i]=tmp[Y[n-i-1].second];

	// おばけの z 座標を三分探索で求める
	double lo=0,hi=1;
	rep(_,40){
		double mi1=(2*lo+hi)/3,mi2=(lo+2*hi)/3,f1,f2;
		G.z=mi1; f1=f(n,C,T,G);
		G.z=mi2; f2=f(n,C,T,G);
		if(f1<f2) hi=mi2; else lo=mi1;
	}
	answer(G.x,G.y,G.z);
}

Submission Info

Judge Result