QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#61935#4497. MapqinjianbinAC ✓394ms4080kbC++2.0kb2022-11-16 00:13:412022-11-16 00:13:45

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-16 00:13:45]
  • 评测
  • 测评结果:AC
  • 用时:394ms
  • 内存:4080kb
  • [2022-11-16 00:13:41]
  • 提交

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

詳細信息

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