QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61908#4497. MapqinjianbinAC ✓307ms3556kbC++172.5kb2022-11-15 21:31:122022-11-15 21:31:13

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-15 21:31:13]
  • 评测
  • 测评结果:AC
  • 用时:307ms
  • 内存:3556kb
  • [2022-11-15 21:31:12]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const double EPS = 1e-2;

struct Point {
	double x, y;
	Point (double x = 0, double y = 0) : x(x), y(y) {}
};
int sgn(double x) {
	return (x < -EPS) ? -1 : (x > EPS);
}

double Cross(Point a, Point b) {
	return a.x * b.y - a.y * b.x;
}
double Cross(Point a, Point b, Point c) {
	return Cross(Point(b.x - a.x, b.y - a.y), Point(c.x - a.x, c.y - b.y));
}

double x[10], y[10];

bool Judge(Point p, Point a, Point b, Point c, Point d) {
	return sgn(Cross(Point(b.x - a.x, b.y - a.y), Point(p.x - a.x, p.y - a.y)) * Cross(Point(d.x - c.x, d.y - c.y), Point(p.x - c.x, p.y - c.y))) == -1;
}

bool check(double x1, double y1)
{
	return (Judge(Point(x1, y1), Point(x[5], y[5]), Point(x[6], y[6]), Point(x[8], y[8]), Point(x[7], y[7])) &&
		Judge(Point(x1, y1), Point(x[5], y[5]), Point(x[8], y[8]), Point(x[6], y[6]), Point(x[7], y[7])));
}

int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		_for(i, 1, 8) scanf("%lf%lf", &x[i], &y[i]);

		//计算k
		double k = (pow(x[1] - x[2], 2) + pow(y[1] - y[2], 2)) / (pow(x[5] - x[6], 2) + pow(y[5] - y[6], 2));

		//直线方程
		double A = 2 * (k * x[5] - k * x[6] - x[1] + x[2]);
		double B = 2 * (k * y[5] - k * y[6] - y[1] + y[2]);
		double C = (x[1] * x[1] + y[1] * y[1] - x[2] * x[2] - y[2] * y[2] - k * (x[5] * x[5] + y[5] * y[5] - x[6] * x[6] - y[6] * y[6]));

		//圆方程
		double a = 1 - k;
		double b = 2 * (k * x[5] - x[1]);
		double c = 1 - k;
		double d = 2 * (k * y[5] - y[1]);
		double e = x[1] * x[1] + y[1] * y[1] - k * x[5] * x[5] - k * y[5] * y[5];

		//一元二次方程
		if(sgn(B))
		{
			double D = -A / B;
			double E = -C / B;
			double ta = a + c * D * D;
			double tb = b + 2 * c * D * E + d * D;
			double tc = c * E * E + d * E + e;

			//解方程
			double x1 = (-tb + sqrt(tb * tb - 4 * ta * tc)) / (2 * ta);
			double y1 = D * x1 + E;
			double x2 = (-tb - sqrt(tb * tb - 4 * ta * tc)) / (2 * ta);
			double y2 = D * x2 + E;

			if(check(x1, y1)) printf("%.10lf %.10lf\n", x1, y1);
			else printf("%.10lf %.10lf\n", x2, y2);
		}
		else
		{
			double X = -C / A;
			e += a * X * X + b * X;
			double ta = c, tb = d, tc = e;
			double y1 = (-tb + sqrt(tb * tb - 4 * ta * tc)) / (2 * ta);
			double y2 = (-tb - sqrt(tb * tb - 4 * ta * tc)) / (2 * ta);

			if(check(X, y1)) printf("%.10lf %.10lf\n", X, y1);
			else printf("%.10lf %.10lf\n", X, y2);
		}
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 307ms
memory: 3556kb

input:

100000
0 5
15 5
15 0
0 0
3 2
9 5
10 3
4 0
-605 604
604 605
605 -604
-604 -605
569 -338
568 -337
569 -336
570 -337
-964 963
963 964
964 -963
-963 -964
-364 838
-365 839
-364 840
-363 839
-664 663
663 664
664 -663
-663 -664
-307 -424
-308 -423
-307 -422
-306 -423
-866 865
865 866
866 -865
-865 -866
12...

output:

6.0000000000 2.0000000000
568.8082644628 -336.2512396694
-364.2463692943 838.3760373447
-306.4503012048 -422.9126506024
119.4705542731 796.6091224024
426.6965648855 50.2398218829
-138.7016574586 -400.8552486188
190.8919117647 -43.8272058823
-392.4260230850 -700.8384050367
96.5101763907 624.641791044...

result:

ok 200000 numbers