Rendezvous on a Tetrahedron

One day, you found two worms $P$ and $Q$ crawling on the surface of a regular tetrahedron with four vertices $A$, $B$, $C$ and $D$. Both worms started from the vertex AA, went straight ahead, and stopped crawling after a while.

When a worm reached one of the edges of the tetrahedron, it moved on to the adjacent face and kept going without changing the angle to the crossed edge (Figure G.1).

Write a program which tells whether or not $P$ and $Q$ were on the same face of the tetrahedron when they stopped crawling.

You may assume that each of the worms is a point without length, area, or volume.

img

Figure G.1. Crossing an edge

Incidentally, lengths of the two trails the worms left on the tetrahedron were exact integral multiples of the unit length. Here, the unit length is the edge length of the tetrahedron. Each trail is more than 0:001 unit distant from any vertices, except for its start point and its neighborhood. This means that worms have crossed at least one edge. Both worms stopped at positions more than 0:001 unit distant from any of the edges.

The initial crawling direction of a worm is specified by two items: the edge $XY$ which is the first edge the worm encountered after its start, and the angle dd between the edge $AX$ and the direction of the worm, in degrees.

img

Figure G.2. Trails of the worms corresponding to Sample Input 1

Figure G.2 shows the case of Sample Input 1. In this case, $P$ went over the edge $CD$ and stopped on the face opposite to the vertex $A$, while $Q$ went over the edge $DB$ and also stopped on the same face.

Input

The input consists of a single test case, formatted as follows.

$X_PY_P$ $d_P$ $ l_P$

$X_QY_Q$ $d_Q$ $l_Q$

$X_WY_W$ ($W=P,Q$) is the first edge the worm $W$ crossed after its start. $X_WY_W$ is one of $BC$, $CD$ or $DB$.

An integer $d_W$ ($1 \leq d_W \leq 59$) is the angle in degrees between edge $AX_W$ and the initial direction of the worm WW on the face $ \Delta AX_WY_W$.

An integer $l_W$ ($1\leq l_W \leq 20$) is the length of the trail of worm $W$ left on the surface, in unit lengths.

Output

Output YES when and only when the two worms stopped on the same face of the tetrahedron. Otherwise, output NO.

Sample Input 1

CD 30 1
DB 30 1

Sample Output 1

YES

Sample Input 2

BC 1 1
DB 59 1

Sample Output 2

YES

Sample Input 3

BC 29 20
BC 32 20

Sample Output 3

NO

Solution

思路

先考虑一只虫子的移动情况。 考虑将这个三角形展开(平铺在一个平面上) 如果从A向BC出发,那么三角形的标号一定形如

A

BC

ADA

BCBC

ADADA

…… 然后判断落点落在哪一个三角形里即可。

不得不说这题很有创意。没有想到展开的话应该也可以做。

Code

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const double eps = 1e-8;
const int N = 10;
struct Point
{
    double x, y;
    Point () {}
    Point (double _x, double _y)
    {
        x = _x;
        y = _y;
    }
};

struct Vector
{
    double x, y;
    Vector () {}
    Vector (double _x, double _y)
    {
        x = _x;
        y = _y;
    }
    double operator * (const Vector &b) const {
        return x * b.x + y * b.y;
    }
    double operator ^ (const Vector &b) const {
        return x * b.y - y * b.x;
    }
};

Vector operator - (const Point &a, const Point &b) {
    return Vector(a.x - b.x, a.y - b.y);
}
Vector operator * (const double a, const Vector &b) 
{
    return Vector(a * b.x, a * b.y);
}
int n;
string str[2]; double d[2], l[2];
void readin()
{
    cin >> str[0] >> d[0] >> l[0];
    cin >> str[1] >> d[1] >> l[1];
}
double angle(double deg)
{
    return deg / 180 * 3.1415926;
}
string get(int n)
{
    double theta = angle(240 + d[n]);
    Vector v = l[n] * Vector(cos(theta), sin(theta));
    int cnt = 0;
    while (v.y < 0)
    {
        v.y += sqrt(3) / 2;
        ++cnt;
    }
    --cnt;
    string s1 = "A";
    string s2 = str[n];
    string temp = "";
    if (str[n] == "DB")
        temp = "CA";
    if (str[n] == "BC")
        temp = "DA";
    if (str[n] == "CD")
        temp = "BA";
    for (int i = 1; i <= 2; ++i)
        s1 = s1 + temp;
    for (int i = 1; i <= 2; ++i)
        s2 = s2 + str[n];
    if (cnt & 1)
        swap(s1, s2);
    
    double x0 = -(double)(cnt + 1) / 2;
    double y = v.y;
    double g = v.x - x0;
    g -= v.y / sqrt(3);
    int tag = -1;
    while (g > 2)
        g -= 2;
    if (g > (1 - 2 * y / sqrt(3)))
    {
        g -= (1 - 2 * y / sqrt(3));
        if (g > 2 * y / sqrt(3))
            g -= 2 * y / sqrt(3);
        else
            tag = 1;
    }
    else 
    {
        tag = 0;
    }
    
    if (tag == -1)
    {
        if (g > (1 - 2 * y / sqrt(3)))
        {
            g -= (1 - 2 * y / sqrt(3));
            if (g > 2 * y / sqrt(3))
                g -= 2 * y / sqrt(3);
            else
                tag = 3;
        }
        else 
        {
            tag = 2;
        }
    }
    string res = "";
    if (tag & 1)
    {
        int a = (tag - 1) / 2;
        res.push_back((char)s1[a]);
        res.push_back((char)s1[a + 1]);
        res.push_back((char)s2[a + 1]);
    }
    else 
    {
        int a = tag / 2;
        res.push_back((char)s2[a]);
        res.push_back((char)s2[a + 1]);
        res.push_back((char)s1[a]);
    }
    return res;
}
void solve()
{   
    string a = get(0);
    string b = get(1);

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    if (a == b)
        puts("YES");
    else
        puts("NO");
}

int main()
{
    readin();
    solve();
    return 0;
}