QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61864 | #4497. Map | qinjianbin | WA | 313ms | 3620kb | C++17 | 2.7kb | 2022-11-15 18:10:01 | 2022-11-15 18:10:03 |
Judging History
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;
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) {
if (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)
return true;
}
bool check(double x1, double y1)
{
if (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])))
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: 313ms
memory: 3620kb
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'