QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61861#4497. MapqinjianbinWA 311ms3496kbC++172.6kb2022-11-15 18:05:482022-11-15 18:05:49

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 18:05:49]
  • 评测
  • 测评结果:WA
  • 用时:311ms
  • 内存:3496kb
  • [2022-11-15 18:05:48]
  • 提交

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-8;

struct Point {
	double x, 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({b.x - a.x, b.y - a.y}, {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) {
	if (sgn(Cross({b.x - a.x, b.y - a.y}, {p.x - a.x, p.y - a.y}) * Cross({d.x - c.x, d.y - c.y}, {p.x - c.x, p.y - c.y})) == -1)
		return true;
}

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

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;
		//	printf("%.1lf %.1lf %.1lf %.1lf %.1lf %.1lf %.1lf\n%.1lf %.1lf %.1lf %.1lf %.1lf %.1lf %.1lf \n", k, A, B, C, a, b, c, d, e, D, E, ta, tb, tc);
		//	puts("!!");


			if(check(x1, y1)) printf("%.10lf %.10lf\n", x1, y1);
			else printf("%.10lf %.10lf\n", x2, y2);
		}
		else
		{
			//puts("!@#!@#");
			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: 0
Wrong Answer
time: 311ms
memory: 3496kb

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:

4.5000000000 3.5000000000
567.2512396694 -337.8108423185
-364.3760373447 838.2462346442
-308.0873493976 -424.5521679478
119.3908775976 796.5293536152
425.7601781171 49.3022422651
-140.1447513812 -402.2999388843
189.8272058823 -44.8934798146
-394.1615949633 -702.5757999947
96.3582089553 624.489617131...

result:

wrong answer 1st numbers differ - expected: '6.0000000', found: '4.5000000', error = '0.2500000'