题意分析

本题要求根据输入的三部分数据（原始记号信息、指令信息、查询信息）建立标记的符号表达式。每个原始记号可能给出坐标（已知）或没有坐标（未知），对于未知记号，可以用一对自由变量$(x1,y1)$表示。后续根据给定的操作指令（求中点、左转、右转）对已有记号的表达式进行线性组合或变换，生成新记号的表达式。最终对查询记号，判断其表达式中是否存在自由变量（即变量系数是否全部为零）。

• 如果所有自由变量的系数均为 $0$（即不含未知数），说明该记号的坐标可以确定，输出计算结果，否则输出 “UNCERTAIN!” 表示目标记号坐标不确定。

解题思路

这道题主要考察对几何知识的理解、对输入数据的处理，以及通过程序代码对符号代数的操作。

1. 输入处理
   这一步需要对输入数据的类型进行判断，然后根据输入的原始记号信息建立每个标记的表达式，对于给出坐标的记号直接记录常数；对于未知记号则用一组自由变量构成其标准基表达式，令每个未知记号对应两个自由变量。

2. 处理指令操作
   根据指令信息，依次对两个记号的表达式进行计算（依据几何知识进行推导，推导过程略）：

   • 类型 $1$：求中点，即 $new = \frac{A+B}{2}$；
   • 类型 $2$：左转操作，根据公式 $new = \bigl((y_A-y_B)+x_B,\;(x_B-x_A)+y_B\bigr)$；
   • 类型 $3$：右转操作，根据公式 $new = \bigl((y_B-y_A)+x_B,\;(x_A-x_B)+y_B\bigr)$。
   • 注意运算时需要同时更新常数项和自由变量的系数。

3. 判断坐标是否可解
   对查询记号的表达式，检查所有自由变量对应的系数是否为 $0$。如果是，则输出计算后的常数坐标；否则输出 “UNCERTAIN!” 表示无法唯一确定。

本题代码

#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <map>
#include <cstdlib>
using namespace std;

struct PointRep {
    double x_const, y_const;
    vector<double> x_coeff, y_coeff;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<string> lines;
    string line;
    while(getline(cin, line)){
        if(line == "END") break;
        if(line.size() == 0) continue;
        lines.push_back(line);
    }
    vector<string> markerLines;
    vector<string> instrLines;
    string queryLine;
    size_t i = 0;
    for(; i < lines.size(); i++){
        istringstream iss(lines[i]);
        string token;
        iss >> token;
        if(token[0] >= '0' && token[0] <= '9'){
            break;
        }
        markerLines.push_back(lines[i]);
    }
    for(; i < lines.size(); i++){
        istringstream iss(lines[i]);
        vector<string> tokens;
        string token;
        while(iss >> token)
            tokens.push_back(token);
        if(tokens.size() == 4){
            instrLines.push_back(lines[i]);
        } else if(tokens.size() == 1){
            queryLine = lines[i];
        }
    }
    int unknownCount = 0;
    vector<string> markerOrder;
    for(size_t j = 0; j < markerLines.size(); j++){
        istringstream iss(markerLines[j]);
        string mark; 
        iss >> mark;
        markerOrder.push_back(mark);
        int dummy;
        if(!(iss >> dummy))
            unknownCount++;
    }
    int globalDim = unknownCount * 2;
    map<string, PointRep> marker;
    int unknownIndex = 0;
    for(size_t j = 0; j < markerLines.size(); j++){
        istringstream iss(markerLines[j]);
        string mark;
        iss >> mark;
        PointRep p;
        p.x_coeff.assign(globalDim, 0.0);
        p.y_coeff.assign(globalDim, 0.0);
        double x, y;
        if(iss >> x >> y){
            p.x_const = x;
            p.y_const = y;
        } else {
            p.x_const = 0.0;
            p.y_const = 0.0;
            if(globalDim > 0){
                p.x_coeff[2 * unknownIndex] = 1.0;
                p.y_coeff[2 * unknownIndex + 1] = 1.0;
            }
            unknownIndex++;
        }
        marker[mark] = p;
    }
    for(size_t j = 0; j < instrLines.size(); j++){
        istringstream iss(instrLines[j]);
        int type;
        string A, B, C;
        iss >> type >> A >> B >> C;
        PointRep pa = marker[A];
        PointRep pb = marker[B];
        PointRep pc;
        pc.x_coeff.assign(globalDim, 0.0);
        pc.y_coeff.assign(globalDim, 0.0);
        if(type == 1){
            pc.x_const = (pa.x_const + pb.x_const) / 2.0;
            pc.y_const = (pa.y_const + pb.y_const) / 2.0;
            for (int k = 0; k < globalDim; k++){
                pc.x_coeff[k] = (pa.x_coeff[k] + pb.x_coeff[k]) / 2.0;
                pc.y_coeff[k] = (pa.y_coeff[k] + pb.y_coeff[k]) / 2.0;
            }
        } else if(type == 2){
            pc.x_const = (pa.y_const - pb.y_const) + pb.x_const;
            pc.y_const = (pb.x_const - pa.x_const) + pb.y_const;
            for (int k = 0; k < globalDim; k++){
                pc.x_coeff[k] = pa.y_coeff[k] - pb.y_coeff[k] + pb.x_coeff[k];
                pc.y_coeff[k] = pb.x_coeff[k] - pa.x_coeff[k] + pb.y_coeff[k];
            }
        } else if(type == 3){
            pc.x_const = (pb.y_const - pa.y_const) + pb.x_const;
            pc.y_const = (pa.x_const - pb.x_const) + pb.y_const;
            for (int k = 0; k < globalDim; k++){
                pc.x_coeff[k] = pb.y_coeff[k] - pa.y_coeff[k] + pb.x_coeff[k];
                pc.y_coeff[k] = pa.x_coeff[k] - pb.x_coeff[k] + pb.y_coeff[k];
            }
        }
        marker[C] = pc;
    }
    istringstream iss(queryLine);
    string query;
    iss >> query;
    PointRep res = marker[query];
    bool unique = true;
    for(int k = 0; k < globalDim; k++){
        if(res.x_coeff[k] != 0.0 || res.y_coeff[k] != 0.0) {
            unique = false;
            break;
        }
    }
    if(unique){
        cout << fixed << setprecision(2) << res.x_const << " " << res.y_const << "\n";
    } else {
        cout << "UNCERTAIN!" << "\n";
    }
    return 0;
}