QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#799072#9576. Ordainer of Inexorable Judgment2317663977WA 1ms4480kbC++2321.7kb2024-12-04 21:33:282024-12-04 21:33:28

Judging History

你现在查看的是最新测评结果

  • [2024-12-23 14:23:26]
  • hack成功,自动添加数据
  • (/hack/1303)
  • [2024-12-06 11:32:56]
  • hack成功,自动添加数据
  • (/hack/1271)
  • [2024-12-04 21:33:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4480kb
  • [2024-12-04 21:33:28]
  • 提交

answer

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cstring>

using ll = long long;

namespace Geo {
	template<typename T>
	class Point;

	template<typename T>
	class Line;

	template<typename T>
	class Polygon;

	template<typename T>
	class Circle;

	template<typename T>
	using Vector = Point<T>;

	template<typename T>
	using Segment = Line<T>;

	template<typename T>
	using PointSet = Polygon<T>;

	const double eps = 1e-9;
	const double PI = acos(-1.0);

	// 浮点数 x 的符号
	template<typename T>
	int sgn(T x) {
		if (fabs(x) < eps) return 0;
		return x > 0 ? 1 : -1;
	}

	// 比较两个浮点数
	template<typename T>
	int cmp(T x, T y) {
		if (fabs(x - y) < eps)return 0; // x == y,返回 0
		else return x < y ? -1 : 1; // x < y,返回 -1; x > y,返回 1
	}

	double radians(double degrees) {
		return degrees * PI / 180.0;
	}

	// 两点距离
	template<typename T>
	double dist(const Point<T>& A, const Point<T>& B) {
		return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
	}

	// 点积
	template<typename T>
	T dot(const Vector<T>& A, const Vector<T>& B) {
		// a · b = |a| |b| cos
		// 可用于判断两向量夹角
		return A.x * B.x + A.y * B.y;
	}

	// 叉积
	template<typename T>
	T cross(const Vector<T>& A, const Vector<T>& B) {
		// a · b = |a| |b| sin
		// 可以判断两向量的相对方向
		// 也能算两向量形成的平行四边形面积
		return A.x * B.y - A.y * B.x;
	}

	// 向量长度
	template<typename T>
	T len(const Vector<T>& A) {
		return sqrt(dot(A, A));
	}

	// 向量长度的平方
	template<typename T>
	T len2(const Vector<T>& A) {
		return dot(A, A);
	}

	// 两向量夹角
	template<typename T>
	double angle(const Vector<T>& A, const Vector<T>& B) {
		return acos(dot(A, B) / len(A) / len(B));
	}

	// 计算两向量构成的平行四边形有向面积
	// 三个点A、B、C,以A为公共点,得到2个向量B-A和C-A,它们构成的平行四边形
	template<typename T>
	T area_parallelogram(const Point<T>& A, const Point<T>& B, const Point<T>& C) {
		return abs(cross(B - A, C - A));
	}

	// 计算两向量构成的平行四边形面积
	// 两个有公共点的向量 A B 构成的平行四边形
	template<typename T>
	T area_parallelogram(const Vector<T>& A, const Vector<T>& B) {
		return abs(cross(A, B));
	}

	// 计算两向量构成的三角形面积
	// 三个点A、B、C,以A为公共点,得到2个向量B-A和C-A,它们构成的三角形
	template<typename T>
	T area_triangle(const Point<T>& A, const Point<T>& B, const Point<T>& C) {
		return abs(cross(B - A, C - A)) / 2.0;
	}

	// 计算两向量构成的三角形有向面积
	// 两个有公共点的向量 A B 构成的三角形
	template<typename T>
	T area_triangle(const Vector<T>& A, const Vector<T>& B) {
		return abs(cross(A, B)) / 2.0;
	}

	// 向量旋转	
	/*
		特殊情况是旋转90度:
		逆时针旋转90度:Rotate(A, pi/2),返回Vector(-A.y, A.x);
		顺时针旋转90度:Rotate(A, -pi/2),返回Vector(A.y, - A.x)。
	*/
	template<typename T>
	Vector<T> rotate(const Vector<T>& A, double rad) {
		return Vector<T>(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
	}

	// 有时需要求单位法向量,即逆时针转90度,然后取单位值。
	template<typename T>
	Vector<T> normal(const Vector<T>& A) {
		return Vector<T>(-A.y / len(A), A.x / len(A));
	}

	// 两个向量是否平行或重合
	template<typename T>
	bool parallel(const Vector<T>& A, const Vector<T>& B) {
		return sgn(cross(A, B)) == 0; // 返回true表示平行或重合
	}

	// 点和直线的位置关系
	template<typename T>
	int point_line_relation(const Point<T>& p, const Line<T>& v) {
		int c = sgn(cross(p - v.p1, v.p2 - v.p1));
		if (c < 0)return 1;              // 1 :p在v的左边
		if (c > 0)return 2;              // 2 :p在v的右边
		return 0;                        // 0 :p在v上
	}

	// 点和线段的位置关系
	template<typename T>
	bool point_segment_relation(const Point<T>& p, const Line<T>& v) {
		// 0 点不在线段v上
		// 1 点在线段v上

		// 前者为 True 说明 p 和 线段 v 的一个端点连边,和 v 本身的夹角为 0,即 p 在 直线 v 上
		// 后者为 True 说明 p 和两端点形成平角,也就是说 p 在两端点之间
		return sgn(cross(p - v.p1, v.p2 - v.p1)) == 0 && sgn(dot(p - v.p1, p - v.p2)) <= 0;
	}

	// 点到直线的距离
	template<typename T>
	double point_line_dis(const Point<T>& p, const Line<T>& v) {
		// 实际上是算了 p 和 v 的一个端点连边,然后和 v 形成的平行四边形的面积,除底得到
		return fabs(cross(p - v.p1, v.p2 - v.p1)) / dist(v.p1, v.p2);
	}

	// 点在直线上的投影
	template<typename T>
	Point<T> point_line_proj(const Point<T>& p, const Line<T>& v) {
		double k = dot(v.p2 - v.p1, p - v.p1) / len2(v.p2 - v.p1);
		return v.p1 + (v.p2 - v.p1) * k;
	}

	// 点关于直线的对称点
	template<typename T>
	Point<T> point_line_symmetry(const Point<T>& p, const Line<T>& v) {
		Point<T> q = point_line_proj(p, v);
		return Point<T>(2 * q.x - p.x, 2 * q.y - p.y);
	}

	// 点到线段的距离
	template<typename T>
	double point_segment_dis(const Point<T>& p, const Segment<T>& v) {
		// 先检查点 p 到线段 v 的投影是否在线段 v 上
		// 如果在,就直接返回点 p 到直线 v 距离
		// 如果不在,就返回线段 v 两端点里 p 

		// p 先和 v 的两端点比较,看看是否两向量夹角 > 90
		if (sgn(dot(p - v.p1, v.p2 - v.p1)) < 0 || sgn(dot(p - v.p2, v.p1 - v.p2)) < 0)
			return min(dist(p, v.p1), dist(p, v.p2)); // 点的投影不在线段上
		return point_line_dis(p, v);           // 点的投影在线段上
	}

	// 叉积判断两条向量的位置关系,AB * AC,两向量共点
	template<typename T>
	int vector_vector_relation(const Vector<T>& v1, const Vector<T>& v2) {
		int sign = sgn(cross(v1, v2));
		if (sign == 0)return 0; // 共线
		if (sign > 0)return 1;  // v2 在 v1 的逆时针方向 
		if (sign < 0)return 2;  // v2 在 v1 的顺时针方向 
	}

	// 叉积判断两条直线的位置关系
	template<typename T>
	int line_line_relation(const Line<T>& v1, const Line<T>& v2) {
		if (sgn(cross(v1.p2 - v1.p1, v2.p2 - v2.p1)) == 0) {
			if (point_line_relation(v1.p1, v2) == 0) return 1;  // 1: 重合
			else return 0;                                      // 0: 平行
		}
		return 2;                                               // 2: 相交
	}

	// 两向量夹角类型
	template<typename T>
	int vector_vector_angle_type(const Vector<T>& v1, const Vector<T>& v2) {
		// 0:夹角度为 0
		// 1:夹角为锐角
		// 2:夹角为钝角
		// 3:夹角为平角,即方向相反
		auto _dot = dot(v1, v2);
		if (vector_vector_relation(v1, v2) == 0) { // 两向量共线
			if (sgn(_dot) > 0)return 0;
			else return 3;
		}
		else {
			if (sgn(_dot) > 0)return 1;
			else return 2;
		}
	}

	// 两条直线的交点
	template<typename T>
	Point<T> line_line_cross_point(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d) {
		// Line1 : ab, Line2 : cd
		double s1 = cross(b - a, c - a);
		double s2 = cross(b - a, d - a);                    // 叉积有正负
		return Point<T>(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
	}

	// 两条直线的交点
	template<typename T>
	Point<T> line_line_cross_point(const Line<T>& x, const Line<T>& y) {
		// Line1 : ab, Line2 : cd
		auto a = x.p1;
		auto b = x.p2;
		auto c = y.p1;
		auto d = y.p2;
		double s1 = cross(b - a, c - a);
		double s2 = cross(b - a, d - a);                    // 叉积有正负
		return Point<T>(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
	}

	// 两个线段是否相交
	template<typename T>
	bool segment_segment_is_cross(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d) {
		// Line1 : ab, Line2 : cd
		double c1 = cross(b - a, c - a), c2 = cross(b - a, d - a);
		double d1 = cross(d - c, a - c), d2 = cross(d - c, b - c);
		return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0;  // 1: 相交;0: 不相交
	}

	// 点和多边形的关系
	template<typename T>
	int point_polygon_relation(const Point<T>& pt, const Polygon<T>& p) {
		// 点pt,多边形 p
		int n = p.size();
		for (int i = 0; i < n; i++) { // 枚举点
			if (p[i] == pt)  return 3;  // 3:点在多边形的顶点上
		}
		for (int i = 0; i < n; i++) { // 枚举边
			Line<T> v = Line<T>(p[i], p[(i + 1) % n]);
			if (point_segment_relation(pt, v)) return 2; // 2:点在多边形的边上
		}

		// 通过射线法计算点是否在多边形内部 (具体原理可以看书)
		int num = 0;
		for (int i = 0; i < n; i++) {
			int j = (i + 1) % n;
			int c = sgn(cross(pt - p[j], p[i] - p[j]));
			int u = sgn(p[i].y - pt.y);
			int v = sgn(p[j].y - pt.y);
			if (c > 0 && u < 0 && v >= 0) num++;
			if (c < 0 && u >= 0 && v < 0) num--;
		}
		return num != 0; // 1:点在内部; 0:点在外部
	}

	// 计算多边形周长
	template<typename T>
	T polygon_perimeter(const Polygon<T>& p) {
		T ans = 0;
		int n = p.size();
		for (int i = 0; i < n; i++)
			ans += dist(p[i], p[(i + 1) % n]);
		return ans;
	}

	// 多边形的面积
	template<typename T>
	T polygon_area(const Polygon<T>& p) {
		/*
			注意面积存在 正负
			逆时针遍历点算出来就是正的
			顺时针遍历点算出来就是负的
		*/
		T area = 0;
		int n = p.size();
		for (int i = 0; i < n; i++)
			area += cross(p[i], p[(i + 1) % n]);
		return abs(area) / 2.0;
	}

	// 多边形的重心
	template<typename T>
	Point<T> polygon_center_point(const Polygon<T>& p) {        //求多边形重心
		Point<T> ans(0, 0);
		int n = p.size();
		if (polygon_area(p, n) == 0) return ans;
		for (int i = 0; i < n; i++)
			ans = ans + (p[i] + p[(i + 1) % n]) * cross(p[i], p[(i + 1) % n]);
		return ans / polygon_area(p, n) / 6;
	}

	/*
	   求凸包,凸包顶点放在ch中
	   凸多边形:是指所有内角大小都在 [0, 180] 范围内的简单多边形
	   凸包:在平面上能包含所有给定点的最小凸多边形叫做凸包
	*/
	template<typename T>
	Polygon<T> convex_hull(vector<Point<T>> p) {
		Polygon<T> ch;

		if (p.size() == 0 or p.size() == 1 or p.size() == 2) {
			for (auto& i : p) ch.push_back(i);
			return ch;
		}

		// Andrew 法:
		// 先对所有点排序
		// 求上下凸包 (查每个边相较于上一条边的拐弯方向)
		// 然后合并
		// 最后得到的点是按照原点的逆时针顺序的

		int n = p.size();
		n = unique(p.begin(), p.end()) - p.begin(); // 去除重复点    
		ch.resize(2 * n);
		sort(p.begin(), p.end());  // 对点排序:按 x 从小到大排序,如果 x 相同,按 y 排序    
		int v = 0;

		// 求下凸包,如果p[i]是右拐弯的,这个点不在凸包上,往回退
		for (int i = 0; i < n; i++) {
			while (v > 1 && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
				v--;
			ch[v++] = p[i];
		}

		// 求上凸包
		for (int i = n - 1, j = v; i >= 0; i--) {
			while (v > j && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
				v--;
			ch[v++] = p[i];
		}
		ch.resize(v - 1);
		return ch;
	}

	// 点和圆的关系,根据点到圆心的距离判断
	template<typename T>
	int point_circle_relation(const Point<T>& p, const Circle<T>& C) {
		double dst = dist(p, C.c);
		if (sgn(dst - C.r) < 0) return 0;       // 0: 点在圆内
		if (sgn(dst - C.r) == 0) return 1;      // 1: 圆上
		return 2;                               // 2: 圆外
	}

	// 直线和圆的关系,根据圆心到直线的距离判断
	template<typename T>
	int line_circle_relation(const Line<T>& v, const Circle<T>& C) {
		double dst = point_line_dis(C.c, v);
		if (sgn(dst - C.r) < 0) return 0;       // 0: 直线和圆相交
		if (sgn(dst - C.r) == 0) return 1;      // 1: 直线和圆相切
		return 2;                               // 2: 直线在圆外
	}

	// 线段和圆的关系,根据圆心到线段的距离判断
	template<typename T>
	int segment_circle_relation(const Segment<T> v, const Circle<T> C) {
		double dst = point_segment_dis(C.c, v);
		if (sgn(dst - C.r) < 0) return 0;       // 0: 线段在圆内
		if (sgn(dst - C.r) == 0) return 1;      // 1: 线段和圆相切
		return 2;                               // 2: 线段在圆外
	}

	//pa, pb是交点。返回值是交点个数
	template<typename T>
	int line_cross_circle(const Line<T>& v, const Circle<T>& C, Point<T>& p1, Point<T>& p2) {
		if (line_circle_relation(v, C) == 2)  return 0;    // 无交点
		Point<T> q = point_line_proj(C.c, v);              // 圆心在直线上的投影点
		double d = point_line_dis(C.c, v);                 // 圆心到直线的距离
		double k = sqrt(C.r * C.r - d * d);
		if (sgn(k) == 0) {                                 // 1个交点,直线和圆相切
			p1 = q;	p2 = q;	return 1;
		}
		Point<T> n = (v.p2 - v.p1) / len(v.p2 - v.p1);     // 单位向量
		p1 = q + n * k;  p2 = q - n * k;
		return 2;                                          // 2个交点
	}

	// 弧度制
	template<typename T>
	double circle_arc_area(const Circle<T>& c, const double& angle) {
		return c.area() * angle / 360.0;
	}

	template<typename T>
	double circle_area(const Circle<T>& c) {
		return c.area();
	}

	// atan2 极角排序,默认逆时针排序
	template<typename T>
	void angle_polar_sort_atan2(vector<Point<T>>& points, const Point<T>& reference = Point<T>(0, 0)) {
		sort(points.begin(), points.end(),
			[&](const Point<T>& a, const Point<T>& b)->bool
			{ return a.polar_angle(reference) < b.polar_angle(reference); });
	}

	// cross 极角排序,默认逆时针排序
	template<typename T>
	void angle_polar_sort_cross(vector<Point<T>>& points, const Point<T>& reference = Point<T>(0, 0)) {
		sort(points.begin(), points.end(),
			[&](Point<T> a, Point<T> b)->bool {
				a = a - reference; b = b - reference;
				if (a.quadrant() != b.quadrant())return a.quadrant() < b.quadrant();
				return sgn(cross(a, b)) > 0; // b 在 a 逆时针方向
			});
	}

	template<typename T>
	class Point {
	private:
		int id;

	public:
		T x, y;

		Point(T x = 0, T y = 0) : x(x), y(y), id(0) {}

		// this 点相较于 reference 点的极角
		// atan2 极角排序有时可能超时,有时反而更快
		double polar_angle(const Point<T>& reference = Point(0, 0)) const {
			return atan2(y - reference.y, x - reference.x);
		}

		T len() const { return sqrt(len2()); } // 向量长度
		T len2() const { return (*this) * (*this); } // 向量长度的平方

		// 求象限,包括了xy正负半轴
		// 可用于叉积法极角排序
		int quadrant() {
			if (x > 0 && y >= 0)return 1;      // 包含了 y 非负半轴
			else if (x <= 0 && y > 0)return 2; // 包含了 x 非正半轴
			else if (x < 0 && y <= 0)return 3; // 包含了 y 非正半轴
			else if (x >= 0 && y < 0)return 4; // 包含了 x 非负半轴
			else return 0; // 原点
		}

		bool hf() {
			return x > 0 || x == 0 && y > 0;
		}
		void set_id(int id) { this->id = id; }
		int get_id()const { return id; }

		Point operator- (const Point& B) const { return Point(x - B.x, y - B.y); }
		Point operator+ (const Point& B) const { return Point(x + B.x, y + B.y); }
		T operator^ (const Point<T>& B) const { return x * B.y - y * B.x; } // 叉积
		T operator* (const Point<T>& B) const { return x * B.x + y * B.y; } // 点积
		Point operator* (const T& B) const { return Point(x * B, y * B); }
		Point operator/ (const T& B) const { return Point(x / B, y / B); }
		bool operator< (const Point& B) const { return x < B.x || (x == B.x && y < B.y); }
		bool operator> (const Point& B) const { return x > B.x || (x == B.x && y > B.y); }
		bool operator== (const Point& B) const { return x == B.x && y == B.y; }
		bool operator!= (const Point& B) const { return !(*this == B); }

		friend ostream& operator<<(ostream& out, const Point& a) {
			out << '(' << a.x << ", " << a.y << ')';
			return out;
		}
	};

	template<typename T>
	class Line {
	public:
		Point<T> p1, p2;                         // 线上的两个点
		Line() {}
		Line(Point<T> p1, Point<T> p2) :p1(p1), p2(p2) {}
		Line(Point<T> p, double angle) {         // 根据一个点和倾斜角 angle 确定直线,0 <= angle < pi
			p1 = p;
			if (sgn(angle - PI / 2) == 0) { p2 = (p1 + Point<T>(0, 1)); }
			else { p2 = (p1 + Point<T>(1, tan(angle))); }
		}
		Line(double a, double b, double c) {     // ax + by + c = 0
			if (sgn(a) == 0) {
				p1 = Point<T>(0, -c / b);
				p2 = Point<T>(1, -c / b);
			}
			else if (sgn(b) == 0) {
				p1 = Point<T>(-c / a, 0);
				p2 = Point<T>(-c / a, 1);
			}
			else {
				p1 = Point<T>(0, -c / b);
				p2 = Point<T>(1, (-c - a) / b);
			}
		}
		friend ostream& operator<<(ostream& out, const Line<T>& a) {
			out << "[" << a.p1 << ", " << a.p2 << "]";
			return out;
		}

		// 计算斜率 k
		double k() const {
			if (sgn(p2.x - p1.x) == 0) { // 垂直线,斜率不存在
				throw runtime_error("Vertical line has undefined slope.");
			}
			return double(p2.y - p1.y) / (p2.x - p1.x);
		}

		// 计算截距 b
		double b() const {
			if (sgn(p2.x - p1.x) == 0) { // 垂直线,斜率不存在
				throw runtime_error("Vertical line does not have a y-intercept.");
			}
			double _k = k();
			return p1.y - _k * p1.x;
		}
	};

	template<typename T>
	class Polygon : public vector<Point<T>> {
	public:
		// 该类可以当点集用,也可以当多边形用。
		// 但注意传入点集不一定逆时针顺序,对于多边形可能需要极角排序

		Polygon() {}
		Polygon(int n) :vector<Point<T>>(n) {}

		// 多边形的周长
		T Perimeter() {
			T ans = 0;
			int n = this->size();
			for (int i = 0; i < n; i++)
				ans += dist((*this)[i], (*this)[(i + 1) % n]);
			return ans;
		}

		// 多边形的面积
		T Area() {
			T area = 0;
			int n = this->size();
			for (int i = 0; i < n; i++) {
				area += cross((*this)[i], (*this)[(i + 1) % n]);
			}
			return abs(area) / 2.0;
		}

		// atan2 极角排序,默认逆时针排序
		void Polar_angle_sort_atan2(const Point<T>& reference = Point<T>(0, 0)) {
			sort(this->begin(), this->end(),
				[&](const Point<T>& a, const Point<T>& b)->bool
				{ return a.polar_angle(reference) < b.polar_angle(reference); });
		}

		// cross 极角排序,默认逆时针排序
		void Polar_angle_sort_cross(const Point<T>& reference = Point<T>(0, 0)) {
			sort(this->begin(), this->end(),
				[&](Point<T> a, Point<T> b)->bool {
					a = a - reference; b = b - reference;
					if (a.quadrant() != b.quadrant())return a.quadrant() < b.quadrant();
					return sgn(cross(a, b)) > 0;
				});
		}

		friend ostream& operator<<(ostream& out, const Polygon<T>& a) {
			out << "[";
			for (int i = 0; i < a.size(); i++)
				out << a[i] << ",]"[i == a.size() - 1];
			return out;
		}
	};

	template<typename T>
	class Circle {
	public:
		Point<T> c;  // 圆心
		T r;         // 半径
		Circle() {}
		Circle(Point<T> c, T r) :c(c), r(r) {}
		Circle(T x, T y, T _r) { c = Point<T>(x, y); r = _r; }
		double area() const { return PI * r * r; }
		// 弧度制
		double arc_area(const double& angle) const { return area() * angle / 360.0; }
		friend ostream& operator<<(ostream& out, const Circle<T>& a) {
			out << "(" << a.c << ", " << a.r << ")";
			return out;
		}
	};
}
using namespace Geo;

const int N = 110;
int n, x, y, d, t;
vector<Point<double>> p;
Polygon<double> poly;

void solve()
{
	cin >> n >> x >> y >> d >> t;
	for (int i = 1;i <= n;i++)
	{
		int a, b;
		cin >> a >> b;
		p.push_back(Point<double>(a, b));
	}
	poly = convex_hull(p);
	poly.Polar_angle_sort_atan2();
	vector<Point<double>> qie;
	for (auto it : poly)
	{
		double jiao = asin(d / dist(it, Point<double>(0, 0)));
		auto dian = rotate(it, jiao);
		qie.push_back(dian);
		dian = rotate(it, -jiao);
		qie.push_back(dian);
	}
	angle_polar_sort_cross(qie);
	//for (auto it : qie)
	//{
	//	cout << it << ' ' << angle(it, Point<double>(1, 0)) << ' ' << it.quadrant() << '\n';
	//}
	auto pl = *qie.begin(), pr = *qie.rbegin();
	double jiajiao = angle(pl, pr);
	int ci = t / (2 * PI);
	double ans = ci * jiajiao;
	double nt = t - ci * 2 * PI;

	//cout << ans << '\n';
	//cout << nt << '\n';

	double chushijiao = angle(Point<double>(x, y), Point<double>(1, 0));
	if (Point<double>(x, y).quadrant() == 4)
		chushijiao += PI;
	else if (Point<double>(x, y).quadrant() == 3)
		chushijiao = 2 * PI - chushijiao;

	//cout << chushijiao << '\n';

	double ljiao = angle(pl, Point<double>(1, 0));
	//cout << ljiao << '\n';
	if (pl.quadrant() == 4)
		ljiao += PI;
	else if (pl.quadrant() == 3)
		ljiao = 2 * PI - ljiao;
	double rjiao = angle(pr, Point<double>(1, 0));
	//cout << rjiao << '\n';
	if (pr.quadrant() == 4)
		rjiao += PI;
	else if (pr.quadrant() == 3)
		rjiao = 2 * PI - rjiao;
	//cout << pr.quadrant() << '\n';

	//cout << ljiao << ' ' << rjiao << '\n';
 
	if (chushijiao <= ljiao)
	{
		if (chushijiao + nt >= rjiao) ans += rjiao - ljiao;
		else if (chushijiao + nt >= ljiao) ans += chushijiao + nt - ljiao;
	}
	else if (chushijiao > rjiao)
	{
		if (chushijiao + nt - 2 * PI >= rjiao) ans += rjiao - ljiao;
		else if (chushijiao + nt - 2 * PI >= ljiao) ans += chushijiao + nt - 2 * PI - ljiao;
	}
	else
	{
		if (chushijiao + nt >= rjiao) ans += rjiao - chushijiao;
		if (chushijiao + nt - 2 * PI >= ljiao) ans += chushijiao + nt - 2 * PI - ljiao;
	}
	//cout << ans << '\n';
	printf("%.10lf\n", ans);
}

int main()
{
	//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T = 1;
	//cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4480kb

input:

3 1 0 1 1
1 2
2 1
2 2

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4428kb

input:

3 1 0 1 2
1 2
2 1
2 2

output:

1.5707963268

result:

ok found '1.5707963', expected '1.5707963', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4384kb

input:

3 1 0 1 10000
1 2
2 1
2 2

output:

2500.7077522575

result:

ok found '2500.7077523', expected '2500.7077523', error '0.0000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 4280kb

input:

3 10000 10000 1 10000
10000 9999
10000 10000
9999 10000

output:

0.3842413013

result:

ok found '0.3842413', expected '0.3842413', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 4252kb

input:

3 -10000 -10000 10000 10000
-10000 -9999
-10000 -10000
-9999 -10000

output:

2500.2404699996

result:

ok found '2500.2404700', expected '2500.2406700', error '0.0000001'

Test #6:

score: 0
Accepted
time: 0ms
memory: 4244kb

input:

4 1 0 1 10000
-2 3400
-4 10000
-4 -10000
-2 -3400

output:

4999.2191154090

result:

ok found '4999.2191154', expected '4999.2191154', error '0.0000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 4416kb

input:

4 1 0 1 10000
-2 3300
-4 10000
-4 -10000
-2 -3300

output:

4999.2003918549

result:

ok found '4999.2003919', expected '4999.2003919', error '0.0000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 4352kb

input:

4 -3040 2716 2147 2
-9033 -8520
-8999 -8533
-8988 -8511
-9004 -8495

output:

0.3508300583

result:

ok found '0.3508301', expected '0.3508301', error '0.0000000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 4412kb

input:

3 8168 -766 1549 1256
-3951 -6425
-3874 -6439
-3911 -6389

output:

84.8328611610

result:

ok found '84.8328612', expected '84.8328612', error '0.0000000'

Test #10:

score: -100
Wrong Answer
time: 0ms
memory: 4256kb

input:

8 2977 -3175 8766 2
-4868 7759
-4867 7925
-4867 7950
-4886 7952
-4979 7953
-5048 7877
-5003 7761
-4936 7759

output:

0.0000000000

result:

wrong answer 1st numbers differ - expected: '0.3278606', found: '0.0000000', error = '0.3278606'