QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61908 | #4497. Map | qinjianbin | AC ✓ | 307ms | 3556kb | C++17 | 2.5kb | 2022-11-15 21:31:12 | 2022-11-15 21:31:13 |
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-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