P1605. Horse Shoe Scoring 题解

题目分析

本题是一个几何计算问题，要求根据马蹄铁的位置计算得分。关键在于判断木桩（原点）与马蹄铁的位置关系，分为四种情况：

1. Ringer（5分）：木桩在马蹄铁内部且不接触
2. Toucher（2分）：马蹄铁与木桩接触
3. Swinger（1分）：马蹄铁绕点B旋转后可能接触木桩
4. 0分：其他情况

解题思路

1. 坐标变换：将马蹄铁的中心点A平移到原点，并旋转坐标系使点B位于y轴上，简化几何计算。
2. 距离计算：计算木桩到马蹄铁各部分的距离，判断位置关系。
3. 得分逻辑：根据距离关系确定得分，按优先级依次判断Ringer、Toucher、Swinger。

代码实现

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

#define sqr(x) ((x) * (x))
#define POLE_RAD 1.0
#define SHOE_RAD 10.0
#define SHOE_CHORD (5.0 * sqrt(2.0))
#define NUM_TOSSES 4

const int RINGER = 5;
const int TOUCHER = 2;
const int SWINGER = 1;

int main() {
    cout << "Turn Score" << endl;
    int turn = 1;

    while (true) {
        int score = 0;
        int shoeCount = 0;

        // 读取当前轮的4次投掷数据
        for (; shoeCount < NUM_TOSSES; ++shoeCount) {
            float ax, ay, bx, by;
            if (!(cin >> ax >> ay >> bx >> by)) {
                if (cin.eof()) {
                    if (turn == 1 && shoeCount == 0) return 0;
                    break;
                } else {
                    cerr << "Invalid input format!" << endl;
                    return 1;
                }
            }

            // 坐标变换：平移和旋转
            float dx = bx - ax;
            float dy = by - ay;
            float len = sqrt(sqr(dx) + sqr(dy));
            float ux = dx / len;
            float uy = dy / len;
            
            // 计算原点在新坐标系中的位置
            float px = -(uy * ax - ux * ay);
            float py = -(ux * ax + uy * ay);
            px = fabs(px);  // 利用对称性简化计算
            
            if (py >= 0) {
                // 情况1：点B在y轴正方向
                float distA = sqr(px) + sqr(py);
                if (distA < sqr(SHOE_RAD - POLE_RAD)) {
                    score += RINGER;  // 木桩在马蹄铁内部
                } else if (distA < sqr(SHOE_RAD + POLE_RAD)) {
                    score += TOUCHER;  // 木桩接触马蹄铁
                } else {
                    float distB = sqr(px) + sqr(py - SHOE_RAD);
                    if (distB <= sqr(SHOE_CHORD + POLE_RAD)) {
                        score += SWINGER;  // 旋转后可能接触
                    }
                }
            } else {
                // 情况2：点B在y轴负方向
                float distLeg = sqr(px - SHOE_RAD) + sqr(py);
                if (distLeg < sqr(POLE_RAD)) {
                    score += TOUCHER;  // 接触直线部分
                } else {
                    float distB = sqr(px) + sqr(py - SHOE_RAD);
                    if (distB <= sqr(SHOE_CHORD + POLE_RAD)) {
                        score += SWINGER;  // 旋转后可能接触
                    }
                }
            }
        }

        if (shoeCount < NUM_TOSSES && !cin.eof()) {
            cerr << "Incomplete turn data!" << endl;
            return 1;
        }

        if (shoeCount == NUM_TOSSES) {
            cout << setw(4) << turn << "  " << setw(4) << score << endl;
            turn++;
        } else {
            break;
        }
    }

    return 0;
}

关键代码解析

1. 坐标变换：

   // 计算向量AB并归一化
   float dx = bx - ax;
   float dy = by - ay;
   float len = sqrt(sqr(dx) + sqr(dy));
   float ux = dx / len;
   float uy = dy / len;
   
   // 计算原点在新坐标系中的坐标
   float px = -(uy * ax - ux * ay);
   float py = -(ux * ax + uy * ay);
   

   通过平移和旋转将马蹄铁转换到标准位置，便于计算。

2. Ringer判断：

   float distA = sqr(px) + sqr(py);
   if (distA < sqr(SHOE_RAD - POLE_RAD)) {
       score += RINGER;
   }
   

   判断木桩到马蹄铁中心的距离是否小于马蹄铁半径减去木桩半径。

3. Toucher判断：

   else if (distA < sqr(SHOE_RAD + POLE_RAD)) {
       score += TOUCHER;
   }
   

   判断木桩到马蹄铁中心的距离是否在接触范围内。

4. Swinger判断：

   float distB = sqr(px) + sqr(py - SHOE_RAD);
   if (distB <= sqr(SHOE_CHORD + POLE_RAD)) {
       score += SWINGER;
   }
   

   判断木桩到点B的距离是否在旋转后的可能接触范围内。

注意事项

1. 输入处理：

   • 程序按轮读取数据，每轮4次投掷
   • 处理了输入结束（EOF）和格式错误的情况

2. 几何计算：

   • 使用平方比较避免开平方运算，提高效率
   • 利用对称性将问题简化为px非负的情况

3. 输出格式：

   • 使用setw控制输出宽度，确保格式正确
   • 轮号和得分右对齐，前导空格填充

通过坐标变换和几何距离计算，程序高效地判断了马蹄铁的得分情况，确保了结果的正确性。