oj.uz

Submission #47558

# Submission time Handle Problem Language Result Execution time Memory
47558 2018-05-05T03:41:22 Z user202729 Experiments with Gorlum (IZhO13_expgorl) C++17
100 / 100
 2 ms 716 KB 
// 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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 2 ms 584 KB Output is correct
7 Correct 2 ms 584 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 584 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Correct 2 ms 716 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 2 ms 716 KB Output is correct
18 Correct 2 ms 716 KB Output is correct
19 Correct 2 ms 716 KB Output is correct
20 Correct 2 ms 716 KB Output is correct