2009 Niuke Summer Multi-School Training Camp (Fifth) - I (Hearing Very Violent)

Problem wormhole: three points 1


Black hole endoscopy:

t group samples, each group of samples input w, h, a, b, c, five numbers and are not greater than 50.

In the coordinate system, 0 <= x <= w, 0 <= y <= h, three points X, Y, Z are found, and | XY| = a, | XZ| = b, | YZ| = c,

Find the coordinates of these three points and output them in turn.


Light years of thinking:

Not quite right at first:

Find the longest edge C (assuming this is c) on the x axis, one end point on (0, 0), and then find the other end point.

If C > x, the edge rotates upward until it touches the edge of the matrix, and then the point is set as the second endpoint.

Then you know two points, three sides, and you can use the cosine theorem and Pythagorean theorem to find the third point.

So the question is which side do you want to put closer to the y axis? (or choose which side of the end to connect to zero (0,0))

I believe that most people like me have the second largest side b (let b be the second largest side)

Then, in this way, the problem will be solved!! Congratulations on wa's death.


In fact, when we think about it, we all made the mistake of taking it for granted. Why?!

Because sometimes you need to put the small side to connect the zero, and the middle side will cause the other end to go beyond the range of wh...

(Why is that?) If you draw your own picture, you will understand that,,,,,, we always take it for granted.

Real practice:

So, it's better to just write a function, every sort of violent abc, accord with the output, (and the title gives always accord with) otherwise continue to look for...

Also, use the inverse function, not the simultaneous cosine Pythagorean equations (wa to doubt life), even if you can find the answer between two partitions...

By the way, the final question on the accuracy of the people do not forget to card you, so, you also need to card at least 1e-6 accuracy range.


#include  <stdio.h>
#include <iostream>
#include      <set>
#include      <map>
#include    <queue>
#include    <stack>
#include   <string>
#include   <math.h>
#include   <vector>
#include  <cstring>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef long long ll;
#define MAXN 3005
#define INF 0x3f3f3f3f3f// nearly half of the maximum ll type, and multiplying 2 will not explode ll
//const ll mod = 9901;
#define mem(a, b) memset(a, b, sizeof(a))
ll mod;

double w, h;
struct node
    double x, y;
} stu[3];

int solution(double a, double b, double c, int x, int y, int z)
    stu[x].x = 0.0;
    stu[x].y = 0.0;
    if(a <= w)
        stu[y].x = a;
        stu[y].y = 0.0;
        stu[y].x = w;
        stu[y].y = sqrt(a*a - w*w);
    double d = acos((a*a+b*b-c*c)*1.0/(2*a*b));//Here we use the inverse function to find the angle.
    d+=atan(stu[y].y*1.0 / stu[y].x);

    stu[z].x = b*cos(d);                       //The coordinates of the last point can be obtained directly by using trigonometric function to know the angle.
    stu[z].y = b*sin(d);

    if(stu[z].x >= 0-1e-8 && stu[z].x <= w+1e-8 && stu[z].y>=0-1e-8 && stu[z].y <= h+1e-8)
    //Pay attention to accuracy or wa.
        printf("%.12f %.12f ", stu[0].x, stu[0].y);
        printf("%.12f %.12f ", stu[1].x, stu[1].y);
        printf("%.12f %.12f\n", stu[2].x, stu[2].y);
        return 1;
    return 0;

int main()
    int t;
    cin >> t;
        double a, b, c;
        scanf("%lf %lf %lf %lf %lf", &w, &h, &a, &b, &c);
        if(solution(a, b, c, 0, 1, 2)) continue;    //Search every situation
        if(solution(a, c, b, 1, 0, 2)) continue;
        if(solution(b, a, c, 0, 2, 1)) continue;
        if(solution(b, c, a, 2, 0, 1)) continue;
        if(solution(c, a, b, 1, 2, 0)) continue;
        if(solution(c, b, a, 2, 1, 0)) continue;
    return 0;


Keywords: iOS

Added by Oubipaws on Sat, 12 Oct 2019 22:19:26 +0300