Submission #34739

---

Source Code Expand

#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;
	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_y(const point<double> &a,const point<double> &b){
	return a.y+EPS<b.y;
}

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);
}

void FindGhost(int n,double Cx[],double Cy[],double Cz[],double Ty[],double Tz[]){
	if(n==1){
		for(;;); // hogera!!
	}

	rep(i,n) if(Cz[i]!=0 || Tz[i]!=0){
		answer(0.0,0.0,0.0);
		return;
	}

	static point<double> C[100000],T[100000]; // candle, target
	rep(i,n){
		C[i]=(point<double>){Cx[i],Cy[i]};
		T[i]=(point<double>){0,Ty[i]};
	}

	sort(C,C+n,cmp_y);
	sort(T,T+n,cmp_y);

	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);
	}

	point<double> ans=get_intersect((line<double>){(point<double>){1,y_min},T[n-1]},
									(line<double>){(point<double>){1,y_max},T[ 0 ]});

	answer(ans.x,ans.y,0);
}

Submission Info

Judge Result