QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61935 | #4497. Map | qinjianbin | AC ✓ | 394ms | 4080kb | C++ | 2.0kb | 2022-11-16 00:13:41 | 2022-11-16 00:13:45 |
Judging History
answer
#include<iostream>
#include<cmath>
using namespace std;
const double EPS = 1e-8;
const double PI = acos(-1);
int sgn(const double x) {return x < -EPS ? -1 : x > EPS;}
int T;
struct Point {
double x, y;
Point (double x = 0, double y = 0) : x(x), y(y) {}
Point operator-(const Point a) { return Point(x - a.x, y - a.y); }
Point operator+(const Point a) { return Point(x + a.x, y + a.y); }
Point operator * (const double r) {return Point (x * r, y * r);}
double len() {return sqrt(x * x + y * y);}
Point rotate(Point p, double ang) {
Point v = (*this) - p;
double c = cos(ang), s = sin(ang);
return Point (p.x + v.x * c - v.y * s, p.y + v.x * s + v.y * c);
}
}p[10];
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 - a, c - a);}
double Dot(Point a, Point b) {return a.x * b.x + a.y * b.y;}
double Dot(Point a, Point b, Point c) { return Dot(b - a, c - a); }
int main() {
scanf("%d", &T);
while (T--) {
for (int i = 1; i <= 8; i++)
scanf("%lf%lf", &p[i].x, &p[i].y);
double ang1 = acos(Dot(p[1], p[2], p[5]) / (p[5] - p[1]).len() / (p[2] - p[1]).len());
double rat1 = (p[5] - p[1]).len() / (p[2] - p[1]).len();
int dir1 = sgn(Cross(p[1], p[2], p[5]));
double ang2 = acos(Dot(p[2], p[1], p[6]) / (p[6] - p[2]).len() / (p[1] - p[2]).len());
double rat2 = (p[6] - p[2]).len() / (p[1] - p[2]).len();
int dir2 = sgn(Cross(p[2], p[1], p[6]));
int Time = 100;
Point p1 = p[5], p2 = p[6];
while (Time--) {
Point tp1 = (p2 - p1) * rat1;
tp1 = tp1.rotate(Point(0, 0), dir1 >= 0 ? ang1 : 2 * PI - ang1) + p1;
Point tp2 = (p1 - p2) * rat2;
tp2 = tp2.rotate(Point(0, 0), dir2 >= 0 ? ang2 : 2 * PI - ang2) + p2;
p1 = tp1;
p2 = tp2;
}
printf("%.10lf %.10lf\n", p1.x, p1.y);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 394ms
memory: 4080kb
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.2463692946 838.3760373444 -306.4503012048 -422.9126506024 119.4705542725 796.6091224018 426.6965648855 50.2398218830 -138.7016574586 -400.8552486188 190.8919117647 -43.8272058824 -392.4260230850 -700.8384050367 96.5101763908 624.641791044...
result:
ok 200000 numbers