Submission #47558

#	Time	Username	Problem	Language	Result	Execution time	Memory
47558		user202729	Experiments with Gorlum (IZhO13_expgorl)	C++17	100 / 100	2 ms	716 KiB

expgorl

// https://oj.uz/problem/view/IZhO13_crazy
#include<iostream>
#include<iomanip>
#include<vector>
#include<array>
#include<cmath>
#include<string>

double sqr(double x){return x*x;}

struct point{
	int x,y;
	point operator+(point p)const{return {x+p.x,y+p.y};}
	point operator-(point p)const{return {x-p.x,y-p.y};}
	point operator*(int   a)const{return {x*a,y*a};}
	point operator-()const{return {-x,-y};}
	double sqrDist(point p)const{return sqr(x-p.x)+sqr(y-p.y);}

	#define m(x,y) ((x)*int64_t(y)) /* multiplication */
	int64_t dot  (point p)const{return m(x,p.x)+m(y,p.y);}
	int64_t cross(point p)const{return m(x,p.y)-m(y,p.x);}
};
std::istream& operator>>(std::istream& str,point& p){
	return str>>p.x>>p.y;
}

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);

	int nRepeat;std::cin>>nRepeat;
	std::string steps;std::cin>>steps;

	point laser,gorlum;std::cin>>laser>>gorlum;
	std::vector<point>shifts={{0,0}};
	shifts.reserve(steps.size()+1);
	for(char c:steps){
		point shift=shifts.back();
		switch(c){
			case 'L':--shift.x;break;
			case 'R':++shift.x;break;
			case 'B':--shift.y;break;
			case 'F':++shift.y;break;
			case 'I':continue;
		}
		shifts.push_back(shift);
	}
	point iterShift=shifts.back(); // gorlum's movement in space in each loop iteration (/nRepeat)
	shifts.pop_back();
	point finalStopPoint=gorlum+iterShift*nRepeat;
	double minSqrDist,maxSqrDist=minSqrDist=laser.sqrDist(finalStopPoint);

	for(point shift:shifts){
		point firstLoc=gorlum+shift;
		point lastLoc =firstLoc+iterShift*(nRepeat-1);

		for(point p:std::array<point,2>{{firstLoc,lastLoc}}){
			maxSqrDist=std::max(maxSqrDist,laser.sqrDist(p));
			minSqrDist=std::min(minSqrDist,laser.sqrDist(p));
		}

		auto a=iterShift.dot(laser-firstLoc),b=iterShift.dot(laser-lastLoc);
		if((a>=0&&b>=0)||(a<=0&&b<=0))continue;

		// now we want to calculate (x) (0 <= x < nRepeat) s.t. 
		// iterShift.dot(laser-(firstLoc+iterShift*x)) is nearest to 0
		point base=laser-firstLoc;
		// == iterShift.dot(base-iterShift*x)
		// == iterShift.dot(base)-iterShift.dot(iterShift)*x
		int x=std::round(iterShift.dot(base)/double(iterShift.dot(iterShift)));
		if(x>=nRepeat)x=nRepeat-1;
		if(x<0)x=0; // make sure that the point is reachable
		point p=firstLoc+iterShift*x;
		minSqrDist=std::min(minSqrDist,laser.sqrDist(p));
	}

	std::cout<<std::fixed<<std::setprecision(10)
		<<std::sqrt(minSqrDist)<<' '<<std::sqrt(maxSqrDist)<<'\n';
}

• Subtask 1: 100 / 100