Warning: session_start(): open(/tmp/sess_db0ff73e84dbd1a9f3a5160addfea48a, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
======小型Matlab的实现方式====== 这个页面用于吐槽多校第四场的一道题目。作为面向对象（Java）大作业感觉不错，建议未来的助教们可以考虑考虑。原型GitHub项目找到了……好像是python写的一个大项目，叫geosolver。 GitHub项目链接：[[https://github.com/uwnlp/geosolver|geosolver]] =====引言与题意===== ZYB对数学有敏锐的直觉，尤其是在几何问题上。几何问题是这样的：求∠CAM的值。或者是这样的：如果AC=x−3，BE=20，AB=16，CD=x+5，求x。为了更容易地分析问题，输入将包含逻辑形式，而不是原始的问题文本和图表。给出若干个符合一定规则的几何题条件。要求出某个角或者某条边或未知数x的值。 =====基本逻辑形式===== * 数字。使用十进制整数表示数字。 * 未知数字。x是唯一未知的数字。 * 表达式（Expression）。表达式可以是一个数字，也可以是一个表达式，其中x只出现一次，最多一次加减法，最多一次乘法。乘法符号可以省略。 * 例如：233，3x+5，x*2+3，x-2是有效表达式，但3x+5-3，x+2x，5*3，2y不是。 * 点。使用单大写字母表示点。 * 线。用Line(Point, Point)来表示一条线（实际上它是一条线段）。 * 例如：Line(A, B)。 * 角。使用Angle(Point, Point, Point)来表示一个角。 * 例如：Angle(A,B,C)。 * 圆。使用Circle(Point)表示具有特定中心的圆。 * 例如：Circle(O)。 * 线段长。使用LengthOf(Line)来获得特定线段的长度值。 * 例如：LengthOf(Line(A, B))。 * 角度。用MeasureOf(Angle)得到特定角度的度数值。 * 例如：MeasureOf(Angle(A,B,C))。 * 项（Term）。项=线段长|角度|表达式。 * 相等。使用Equals(Term,Term)来声明这两个项的值相等。 * 例如：Equals(LengthOf(A,B), 2)、Equals(MeasureOf(Angle(A, B, C))。 * 垂直。使用Perpendicular(Line, Line)表示两条垂直线。 * 例如：Perpendicular(Line (A, C), Line(B, D))。 * 平行。使用Parallel(Line,Line)表示两条平行线。保证各点都是有序的。 * 例如：Parallel(Line (A, C), Line(B, D))。 * 点在线上。使用PointLiesOnLine(Point, Line)来表示位于直线上的点。 * 例如：PointLiesOnLine(A, Line(B, C))。 * 点在圆上。使用PointLiesOnCircle(Point, Circle)表示位于圆上的点。 * 例如：PointLiesOnCircle(A, Circle(O))。 * 问题。使用Find(Term)来询问给定项的确切值。 * 例如：Find(x)、Find(LengthOf(Line(A,B)))。请注意，图和文本中的所有条件都将转换为逻辑形式。你现在得到了一个只有一个问题（Find phrase）的逻辑表单列表，并希望找到解决方案。 =====定理===== * 平角定理：如果点C位于AB上，则∠ACB=180∘。 * 等腰三角形定理：在三角形ABC中，如果AB=AC，则∠ACB=∠ABC，反之亦然。 * 三角形内角和定理：任何三角形的三个内角加起来等于180∘。 * 勾股定理：在直角三角形中，如果三条边的长度分别是a，b，c（其中c是斜边），那么a^2+b^2=c^2。 * 这个定理的逆定理也成立，但是暂时用不到。 * 全等三角形定理：两个三角形满足下列条件时为全等。 * SSS：如果三条边对应相等，则两个三角形全等。 * SAS：如果两边及其夹角对应相等，则两个三角形全等。 * AAS和ASA：如果有两个对应角相等（相似），又有一组对应边相等，则两个三角形全等。 * HL：对应斜边和对应直角边相等的两个直角三角形全等。 * 在全等三角形中，对应边和对应角相等。 * 相似三角形定理：两个三角形在满足以下条件时是相似的。 * SSS：三条对应边成比例的两个三角形相似。 * SAS：两条对应边成比例，且夹角相等，则两个三角形相似。 * AA：两个对应角相等的两个三角形相似。 * HL：对应斜边和对应直角边成比例的两个直角三角形相似。 * 在相似三角形中，对应角相等，对应边成比例。 * 平行线定理：如果两条直线平行，则同位角（corresponding）相等，内错角（alternate）相等，同旁内角（interior）互补（supplementary）。 * 直径相等定理：同一个圆的不同直径相等。圆的中心也是每个直径的中点。 * 圆上点定理：如果AB是圆O的直径，另一个点C位于圆O上，则∠ACB=90∘。 =====建议===== * 逻辑形式可以嵌套。 * 保证每个案例至少有一个好的解决方案。一个好的解决方法是：你可以用上面的定理一步一步地解决问题；每一步之后，你获得的新值都是有效表达式（这也意味着表达式中涉及的数字总是整数）；步骤数不超过4。 * 给定的逻辑形式是充分的。 * 例如：如果一个段上有四个点A，B，C，D，那么将列出四个相应的PointLiesOnLine短语（A-B-C，A-B-D，A-C-D，B-C-D）。 * 例如：如果给你一个短语Perpendicular(Line (A, C), Line(B, D))，这两条线的交集也会给出。 * 即：PointLiesOnLine(E, Line(A, C))和PointLiesOnLine(E, Line(B, D))，如果交集是E。 * 如果AO、BO、CO是三个不同的线段，则很难检测哪个线段位于中间。在这个问题中，您不需要在∠AOB、∠AOC、∠BOC之间建立关系。 * 除非在这种明显的情况下：如果B位于AC上，则可以使用∠AOC=∠AOB+∠BOC。 * 所有的数据都来自现实世界的问题，而不是人工构建的。 * 总共有20个问题。从中选取样本（包括10个问题）。 =====输入输出描述===== 输入包含多个样例。输入的第一行包含一个整数T（总是5），即样例数。对于每个样例，第一行包含一个整数N（3≤N≤12），表示逻辑形式的数量。第二行包含几个以空格分隔的大写字母，表示与此问题相关的所有点。第三行包含几个长度为2的大写字母字符串，表示与此问题相关的所有直线（线段）。在接下来的N行中，有一个字符串si（|si|≤50），表示第i个逻辑形式。保证最后一个逻辑形式以“Find”开头。对于每种情况，输出一个表示答案的整数。不应该牵涉到未知的数字。 =====样例一=====



5
11
N M B C T A D
MA MB MT MD AB AC BC TC TN CN
Equals(MeasureOf(Angle(M, T, N)), 28)
PointLiesOnLine(B, Line(A, C))
PointLiesOnLine(D, Line(T, N))
PointLiesOnCircle(N, Circle(M))
PointLiesOnCircle(C, Circle(M))
PointLiesOnCircle(T, Circle(M))
PointLiesOnCircle(A, Circle(M))
Perpendicular(Line(A, B), Line(M, B))
Perpendicular(Line(D, M), Line(T, D))
Equals(LengthOf(Line(B, M)), LengthOf(Line(D, M)))
Find(MeasureOf(Angle(C, A, M)))
8
A B C D E
AC AD AB AE BC BE CD DE
Equals(LengthOf(Line(A, C)), x-3)
Equals(LengthOf(Line(A, B)), 16)
Equals(LengthOf(Line(C, D)), x+5)
Equals(LengthOf(Line(B, E)), 20)
PointLiesOnLine(C, Line(A, D))
PointLiesOnLine(B, Line(A, E))
Parallel(Line(B, C), Line(E, D))
Find(x)
12
A B C D F
CB CD CA CF BD BA BF DA DF AF
Equals(MeasureOf(Angle(F, A, D)), 20)
Equals(LengthOf(Line(D, A)), 9)
Equals(MeasureOf(Angle(F, A, B)), 32)
Equals(LengthOf(Line(B, A)), 6)
Equals(MeasureOf(Angle(A, D, B)), 40)
PointLiesOnLine(F, Line(C, A))
PointLiesOnLine(F, Line(B, D))
Parallel(Line(A, D), Line(B, C))
Equals(LengthOf(Line(A, D)), LengthOf(Line(B, C)))
Parallel(Line(A, B), Line(D, C))
Equals(LengthOf(Line(A, B)), LengthOf(Line(D, C)))
Find(MeasureOf(Angle(D, B, A)))
5
A B C
AB BC AC
Equals(LengthOf(Line(A, B)), 2x-7)
Equals(LengthOf(Line(B, C)), 4x-21)
Equals(LengthOf(Line(A, C)), x-3)
Equals(LengthOf(Line(A, B)), LengthOf(Line(B, C)))
Find(LengthOf(Line(A, C)))
5
A B C
AB AC BC
Equals(LengthOf(Line(A, C)), 3)
Equals(LengthOf(Line(A, B)), 5)
Equals(LengthOf(Line(B, C)), x)
Perpendicular(Line(A, C), Line(B, C))
Find(x)

28
35
88
4
4

=====样例二=====



5
7
A C B D E
AB AC AE AD BE BC DE CD
Equals(LengthOf(Line(A, C)), 16)
Equals(LengthOf(Line(E, D)), 5)
Equals(LengthOf(Line(A, B)), 12)
PointLiesOnLine(B, Line(A, C))
Parallel(Line(C, D), Line(B, E))
PointLiesOnLine(E, Line(A, D))
Find(LengthOf(Line(A, E)))
12
A B C D F
CB CD CA CF BD BA BF DA DF AF
Equals(MeasureOf(Angle(F, A, D)), 20)
Equals(LengthOf(Line(D, A)), 9)
Equals(MeasureOf(Angle(F, A, B)), 32)
Equals(LengthOf(Line(B, A)), 6)
Equals(MeasureOf(Angle(D, B, C)), 40)
PointLiesOnLine(F, Line(C, A))
PointLiesOnLine(F, Line(B, D))
Parallel(Line(A, D), Line(B, C))
Equals(LengthOf(Line(A, D)), LengthOf(Line(B, C)))
Parallel(Line(A, B), Line(D, C))
Equals(LengthOf(Line(A, B)), LengthOf(Line(D, C)))
Find(MeasureOf(Angle(A, D, C)))
12
A B C D E F G
GC GD GB GF GA GE CE BF BA FA
Equals(MeasureOf(Angle(A, G, C)), 60)
PointLiesOnLine(F, Line(G, A))
PointLiesOnLine(G, Line(C, E))
PointLiesOnLine(G, Line(B, F))
PointLiesOnLine(G, Line(B, A))
PointLiesOnLine(F, Line(B, A))
PointLiesOnCircle(C, Circle(G))
PointLiesOnCircle(B, Circle(G))
PointLiesOnCircle(A, Circle(G))
PointLiesOnCircle(E, Circle(G))
Perpendicular(Line(G, F), Line(G, D))
Find(MeasureOf(Angle(B, G, E)))
3
A B C
AB AC BC
Equals(MeasureOf(Angle(A, B, C)), 40)
Equals(MeasureOf(Angle(C, A, B)), 25)
Find(MeasureOf(Angle(B, C, A)))
6
D A B K G
KG GD DA KA AB KB
Equals(MeasureOf(Angle(B, A, D)), 3x-70)
Equals(MeasureOf(Angle(K, G, D)), 120)
Equals(MeasureOf(Angle(G, D, A)), x)
Parallel(Line(K, G), Line(A, D))
PointLiesOnLine(A, Line(K, B))
Find(x)

15
128
60
115
60

=====核心思路===== 题目保证了每一步的结果依然是 expressions。我们不断用已知的条件和定理扩展我们知道的量，直到找到答案。中途可能需要构方程和解方程。整个过程有点像迭代加深搜索。 =====注意点===== 同一个角的表示有很多种，注意要对它们建立Equal关系。对于所有 PointLiesOnLine，要构建边长相加的 Equal 关系和角度相加的 Equal 关系。对于平行线，同位角可能不存在，所以可以只用内错角和同旁内角建立关系。可以先不断地用“基本定理”传播 expression，到最后再用勾股定理、相似定理等复杂的定理解方程。要能检测出图中的三角形（只要三点不共线就算），并积极寻找全等和相似的三角形对。在运用一些定理时，所用的条件可能不是“完全”的。比如我们知道两条边的长度都是 2x+3，我们依然可以利用它们相等来构建对角相等或者三角形全等的关系。可以用 Find 导向去优化搜索方向。不过这道题是不必要的，你把所有可以求的量求出来也是 OK 的。在解出 x 后，要把之前所有用 x 表示的表达式都带入一遍。复杂度为所有状态量 * 定理数量 * 步数上限（4）。 =====目前的代码===== 其中auto关键字需要C++11才能通过编译。目前情况是“运行错误”。这是因为在代码末尾有一个throw。代码可以通过两个给出样例，但是如果注释掉throw会“答案错误”，只能通过50%的样例。代码中还有两个被注释掉的throw，去掉注释完全不影响，说明可能不是读入与判断相等层次的问题，可能是其他逻辑问题。建议参考一下命题人的其他提示，并检查代码的相应部分是否按照出题人提示完成了。



#include
#include
#include

#include
#include
#include

#include
#include
#include
#include
#include
#include
#include

using namespace std;

#define REP(_i,_a,_n) for(int _i=_a;_i<=_n;++_i)

int Value=1e8;

vector BasePoint;
struct Expression {
    int x,y;
    Expression () {}
    Expression (int x, int y) :x(x),y(y) {}
    bool operator == (const Expression & b) const {return x==b.x&&y==b.y;}
    bool operator != (const Expression & b) const {return x!=b.x||y!=b.y;}
    Expression operator + (const Expression & b) {
        return Expression(x+b.x,y+b.y);
    }
    Expression &operator += (const Expression & b) {
        return *this=*this+b;
    }
    Expression operator - (const Expression & b) {
        return Expression(x-b.x,y-b.y);
    }
    Expression &operator -= (const Expression & b) {
        return *this=*this-b;
    }
};
struct Line {
    char x,y;
    Line (char x=0, char y=0) :x(x),y(y) {}
    Line repr() const {
        Line u = *this;
        if (u.x>u.y) swap(u.x,u.y);
        return u;
    }
    bool operator == (const Line &b) const {return x==b.x&&y==b.y;}
    bool operator != (const Line &b) const {return x!=b.x||y!=b.y;}
    bool operator < (const Line &b) const {
        Line u = this->repr();
        Line v = b.repr();
        if (u.x!=v.x) return u.x BaseLine;
map length;
map length2;
map,int> parallel;
map,int> perpendicular;
map > Point_Line;
struct Angle {
    char x,y,z;
    Angle (char x=0, char y=0, char z=0) :x(x),y(y),z(z) {}
    Angle repr() const {
        Angle u = *this;
        if (u.x>u.z) swap(u.x,u.z);
        return u;
    }
    bool operator < (const Angle & b) const {
        Angle u = this->repr();
        Angle v = b.repr();
        if (u.x!=v.x) return u.x degree;
map degree2;
map BaseAngle;
struct Triangle {
    char x,y,z;
    Triangle (char x=0, char y=0, char z=0) :x(x),y(y),z(z) {}
    bool operator < (const Triangle & b) const {
        if (x!=b.x) return x BaseTriangle;

map > Point_Circle;
struct Term {
    int type;
    Line l;
    Angle ang;
    Expression val;
} Question;
struct Line_Equation {
    int var1, var2, var3, var4;
    Expression val;
};
int Line_fa[5555];
int Angle_fa[5555];
int Find(int fa[5555], int x) {return fa[x]==x?x:fa[x]=Find(fa,fa[x]);}
//0, l1=l2
//1, l1+l2=l3
//2, l1^2+l2^2=l3^2
//3, l1/l2=l3/l4
vector Base_Line_Equation[4];
struct Angle_Equation {
    int var1, var2, var3;
};
//0, a1=a2
//1, a1+a2=180
//2, a1+a2=a3
//3, a1+a2+a3=180
vector Base_Angle_Equation[4];
struct Logic_Form {
    char p;
    Line l;
    Angle ang;
    char c;
    Term t;
};
int CreatePoint(char x) {
    for (auto &y:BasePoint) if (y==x) return 0;
    BasePoint.push_back(x);
    return 1;
}
int CreateLine(Line l) {
    if (BaseLine.count(l)) return BaseLine[l];
    int t = BaseLine.size();
    sourceLine[t+1] = l;
    return BaseLine[l] = t+1;
}
int CreateAngle(Angle a) {
    if (BaseAngle.count(a)) return BaseAngle[a];
    int t = BaseAngle.size();
    sourceAngle[t+1] = a;
    return BaseAngle[a] = t+1;
}
int CreateTriangle(Triangle a) {
    if (BaseTriangle.count(a)) return BaseTriangle[a];
    int t = BaseTriangle.size();
    sourceTriangle[t+1] = a;
    return BaseTriangle[a] = t+1;
}
bool isEqual(Angle a, int b) {
    return degree.count(a)&°ree[a]==b;
}
bool isEqual(Angle a, Angle b) {
    if (degree.count(a)&°ree.count(b)) return degree[a]==degree[b];
    if (degree2.count(a)&°ree2.count(b)) return degree2[a]==degree2[b];
    int u = Find(Angle_fa, CreateAngle(a)), v = Find(Angle_fa, CreateAngle(b));
    return u==v;
}
bool isEqual(Line a, Line b) {
    if (length.count(a)&&length.count(b)) return length[a]==length[b];
    if (length2.count(a)&&length2.count(b)) return length2[a]==length2[b];
    int u = Find(Line_fa, CreateLine(a)), v = Find(Line_fa, CreateLine(b));
    return u==v;
}
void getValue(int x) {
    if (Value!=1e8) return;
    Value = x;
    for (auto &t:degree2) {
        auto v = t.second;
        degree[t.first] = Value*v.x+v.y;
    }
    degree2.clear();
    for (auto &t:length2) {
        auto v = t.second;
        length[t.first] = Value*v.x+v.y;
    }
    length2.clear();
}
//a=b
void getValue(Expression a, Expression b) {
    if (Value!=1e8) return;
    if (a==b) return;
    getValue((b.y-a.y)/(a.x-b.x));
}
//a+b=c
void getValue(Expression a, Expression b, Expression c) {
    if (Value!=1e8) return;
    getValue(a+b,c);
}
//ax+b=0
void getValue(int a, int b) {
    if (a==0||Value!=1e8) return;
    int x = -b/a;
    if (x>=0&&a*x+b==0) return getValue(x);
}
//ax^2+bx+c=0
void getValue(int a, int b, int c) {
    if (Value!=1e8) return;
    if (a==0) return getValue(b,c);
    double delta = sqrt(b*b-4*a*c);
    int x1 = (-b+delta)/(2*a), x2 = (-b-delta)/(2*a);
    if (x1>=0&&(long long)a*x1*x1+(long long)b*x1+c==0) return getValue(x1);
    if (x2>=0&&(long long)a*x2*x2+(long long)b*x2+c==0) return getValue(x2);
}
//a=b
void LineEquation(Line a, int b) {
    a = sourceLine[Find(Line_fa,CreateLine(a))];
    if (length2.count(a)) getValue(length2[a],Expression(0,b));
    length[a] = b;
}
//a=b
void LineEquation(Line a, Expression b) {
    if (b.x==0) return LineEquation(a,b.y);
    if (Value!=1e8) return LineEquation(a,b.y+b.x*Value);
    a = sourceLine[Find(Line_fa,CreateLine(a))];
    if (length2.count(a)) return getValue(length2[a],b);
    length2[a] = b;
}
//a=b
void LineEquation(Line a, Line b) {
    if (isEqual(a,b)) return;
    int u = Find(Line_fa,CreateLine(a)), v = Find(Line_fa,CreateLine(b));
    a = sourceLine[u], b = sourceLine[v];
    if (length.count(a)) {
        Line_fa[v] = u;
        return;
    }
    if (length.count(b)) {
        Line_fa[u] = v;
        return;
    }
    if (length2.count(a)&&length2.count(b)) {
        Line_fa[u] = v;
        return getValue(length2[a],length2[b]);
    }
    if (length2.count(a)) {
        Line_fa[v] = u;
        return;
    }
    if (length2.count(b)) {
        Line_fa[u] = v;
        return;
    }
    Line_fa[u] = v;
}
//a+b=c
map,Line> Base_Line_Equation2;
//a-b=c
map,Line> Base_Line_Equation3;
void LineEquation(Line a, Line b, Line c) {
    if (b,Line>,Line> Base_Line_Equation4;
void LineEquation(Line a, Line b, Line c, Line d) {
    if (isEqual(a,c)) return LineEquation(b,d);
    if (isEqual(b,d)) return LineEquation(a,c);
    if (isEqual(a,b)) return LineEquation(c,d);
    if (isEqual(c,d)) return LineEquation(a,b);
    pair,Line> ret = {{a,b},c};
    if (Base_Line_Equation4.count(ret)) {
        LineEquation(Base_Line_Equation4[ret],d);
    }
    else Base_Line_Equation4[ret]=d;
}
void AngleEquation(Angle a, int b) {
//  printf("[%c%c%c]=%d\n",a.x.x,a.y.x,a.z.x,b);
    a = sourceAngle[Find(Angle_fa,CreateAngle(a))];
    if (degree2.count(a)) getValue(degree2[a],Expression(0,b));
    degree[a] = b;
}
void AngleEquation(Angle a, Expression b) {
    if (b.x==0) return AngleEquation(a,b.y);
    if (Value!=1e8) return AngleEquation(a,b.y+b.x*Value);
    a = sourceAngle[Find(Angle_fa,CreateAngle(a))];
    if (degree2.count(a)) return getValue(degree2[a],b);
    degree2[a] = b;
}
void AngleEquation(Angle a, Angle b) {
//  printf("[%c%c%c]=[%c%c%c]\n",a.x.x,a.y.x,a.z.x,b.x.x,b.y.x,b.z.x);
    if (isEqual(a,b)) return;
    int u = Find(Angle_fa,CreateAngle(a)), v = Find(Angle_fa,CreateAngle(b));
    a = sourceAngle[u], b = sourceAngle[v];
    if (degree.count(a)) {
        Angle_fa[v] = u;
        return;
    }
    if (degree.count(b)) {
        Angle_fa[u] = v;
        return;
    }
    if (degree2.count(a)&°ree2.count(b)) {
        Angle_fa[u] = v;
        return getValue(degree2[a],degree2[b]);
    }
    if (degree2.count(a)) {
        Angle_fa[v] = u;
        return;
    }
    if (degree2.count(b)) {
        Angle_fa[u] = v;
        return;
    }
    Angle_fa[u] = v;
}
//a+b=180
map Base_Angle_Equation2;
void AngleEquation2(Angle a, Angle b) {
//  printf("[%c%c%c]+[%c%c%c]=180\n",a.x.x,a.y.x,a.z.x,b.x.x,b.y.x,b.z.x);
    if (isEqual(a,b)) return AngleEquation(a,90),AngleEquation(b,90);
    if (Base_Angle_Equation2.count(a)) {
        AngleEquation(Base_Angle_Equation2[a],b);
    }
    else Base_Angle_Equation2[a]=b;
    if (Base_Angle_Equation2.count(b)) {
        AngleEquation(Base_Angle_Equation2[b],a);
    }
    else Base_Angle_Equation2[b]=a;
}
//a+b=c
map,Angle> Base_Angle_Equation3;
//a-b=c
map,Angle> Base_Angle_Equation4;
void AngleEquation(Angle a, Angle b, Angle c) {
//  printf("[%c%c%c]+[%c%c%c]=[%c%c%c]\n",a.x.x,a.y.x,a.z.x,b.x.x,b.y.x,b.z.x,c.x.x,c.y.x,c.z.x);
    if (bpos) {
        int num = 0;
        REP(i,sign_pos+1,r) {
            if (isdigit(s[i])) num=num*10+s[i]-'0';
        }
        int x = 1, tmp = 0;
        REP(i,l,pos-1) {
            if (isdigit(s[i])) tmp=tmp*10+s[i]-'0';
        }
        if (tmp) x *= tmp;
        tmp = 0;
        REP(i,pos+1,sign_pos-1) {
            if (isdigit(s[i])) tmp=tmp*10+s[i]-'0';
        }
        if (tmp) x *= tmp;
        if (Value==1e8) log.t.val = Expression(x,sign*num);
        else log.t.val = Expression(0,sign*num+x*Value);
        return log;
    }
//    throw;
}
//a/b=c/d
void solveProportional(Line a, Line b, Line c, Line d) {
    a = sourceLine[Find(Line_fa,CreateLine(a))];
    b = sourceLine[Find(Line_fa,CreateLine(b))];
    c = sourceLine[Find(Line_fa,CreateLine(c))];
    d = sourceLine[Find(Line_fa,CreateLine(d))];
    Expression va=length.count(a)?Expression(0,length[a]):length2.count(a)?length2[a]:Expression(1e8,1e8);
    Expression vb=length.count(b)?Expression(0,length[b]):length2.count(b)?length2[b]:Expression(1e8,1e8);
    Expression vc=length.count(c)?Expression(0,length[c]):length2.count(c)?length2[c]:Expression(1e8,1e8);
    Expression vd=length.count(d)?Expression(0,length[d]):length2.count(d)?length2[d]:Expression(1e8,1e8);
    if ((va+vb+vc+vd).y>=1.5e8) return;
    if (va.y==1e8) {
        //a=cb/d
        if (vd.x==0&&(long long)vc.y*vb.y%vd.y==0) {
            if (vc.x==0&&vb.x==0) LineEquation(a,(long long)vc.y*vb.y/vd.y);
            else if (vc.x==0) {
                if ((long long)vc.y*vb.x%vd.y==0) {
                    LineEquation(a,Expression((long long)vc.y*vb.x/vd.y,(long long)vc.y*vb.y/vd.y));
                }
            }
            else if (vb.x==0) {
                if ((long long)vb.y*vc.x%vd.y==0) {
                    LineEquation(a,Expression((long long)vb.y*vc.x/vd.y,(long long)vc.y*vb.y/vd.y));
                }
            }
        }
        return;
    }
    if (vb.y==1e8) {
        //b=ad/c
        if (vc.x==0&&(long long)va.y*vd.y%vc.y==0) {
            if (va.x==0&&vd.x==0) LineEquation(b,(long long)va.y*vd.y/vc.y);
            else if (va.x==0) {
                if ((long long)va.y*vd.x%vc.y==0) {
                    LineEquation(b,Expression((long long)va.y*vd.x/vc.y,(long long)va.y*vd.y/vc.y));
                }
            }
            else if (vd.x==0) {
                if ((long long)vd.y*va.x%vc.y==0) {
                    LineEquation(b,Expression((long long)vd.y*va.x/vc.y,(long long)va.y*vd.y/vc.y));
                }
            }
        }
        return;
    }
    if (vc.y==1e8) {
        //c=ad/b
        if (vb.x==0&&(long long)va.y*vd.y%vb.y==0) {
            if (va.x==0&&vd.x==0) LineEquation(c,(long long)va.y*vd.y/vb.y);
            else if (va.x==0) {
                if ((long long)va.y*vd.x%vb.y==0) {
                    LineEquation(c,Expression((long long)va.y*vd.x/vb.y,(long long)va.y*vd.y/vb.y));
                }
            }
            else if (vd.x==0) {
                if ((long long)vd.y*va.x%vb.y==0) {
                    LineEquation(c,Expression((long long)vd.y*va.x/vb.y,(long long)va.y*vd.y/vb.y));
                }
            }
        }
        return;
    }
    if (vd.y==1e8) {
        //d=cb/a
        if (va.x==0&&(long long)vc.y*vb.y%va.y==0) {
            if (vc.x==0&&vb.x==0) LineEquation(d,(long long)vc.y*vb.y/va.y);
            else if (vc.x==0) {
                if ((long long)vc.y*vb.x%va.y==0) {
                    LineEquation(d,Expression((long long)vc.y*vb.x/va.y,(long long)vc.y*vb.y/va.y));
                }
            }
            else if (vb.x==0) {
                if ((long long)vb.y*vc.x%va.y==0) {
                    LineEquation(d,Expression((long long)vb.y*vc.x/va.y,(long long)vc.y*vb.y/va.y));
                }
            }
        }
        return;
    }
    //a.xd.xX^2+a.x*d.yX+a.y*d.xX+a.y*d.y=c.xb.xX^2+c.yb.xX+c.xb.yX+c.yb.y
    //(a.xd.x-c.xb.x) X^2 + (a.x*d.y+a.y*d.x-c.yb.x-c.xb.y) X + a.yd.y-c.yb.y = 0
    getValue(va.x*vd.x-vc.x*vb.x,va.x*vd.y+va.y*vd.x-vc.y*vb.x-vc.x*vb.y,va.y*vd.y-vc.y*vb.y);
}
void solveAngle() {
    int tot = BaseAngle.size();
    REP(i,1,tot) {
        Angle u = sourceAngle[Find(Angle_fa,i)];
        if (degree.count(u)) degree[sourceAngle[i]]=degree[u];
        else if (degree2.count(u)) degree2[sourceAngle[i]]=degree2[u];
    }
    for (auto &e:Base_Angle_Equation2) {
        auto L = e.first, R = e.second;
        L = sourceAngle[Find(Angle_fa,CreateAngle(L))];
        R = sourceAngle[Find(Angle_fa,CreateAngle(R))];
        if (isEqual(L,R)) {
            AngleEquation(L,90);
            AngleEquation(R,90);
            continue;
        }
        if (degree.count(L)) {
            AngleEquation(R,180-degree[L]);
            continue;
        }
        if (degree.count(R)) {
            AngleEquation(L,180-degree[R]);
            continue;
        }
        if (degree2.count(L)&°ree2.count(R)) {
            getValue(degree2[L],degree2[R],Expression(0,180));
            continue;
        }
        if (degree2.count(L)) {
            AngleEquation(R,Expression(0,180)-degree2[L]);
            continue;
        }
        if (degree2.count(R)) {
            AngleEquation(L,Expression(0,180)-degree2[R]);
            continue;
        }
    }
    for (auto &e:Base_Angle_Equation3) {
        auto u = e.first.first, v = e.first.second, w = e.second;
        u = sourceAngle[Find(Angle_fa,CreateAngle(u))];
        v = sourceAngle[Find(Angle_fa,CreateAngle(v))];
        w = sourceAngle[Find(Angle_fa,CreateAngle(w))];
        if (degree.count(u)&°ree.count(v)) {
            AngleEquation(w,degree[u]+degree[v]);
            continue;
        }
        if (degree.count(u)&°ree.count(w)) {
            AngleEquation(v,degree[w]-degree[u]);
            continue;
        }
        if (degree.count(v)&°ree.count(w)) {
            AngleEquation(u,degree[w]-degree[v]);
            continue;
        }
        if (degree.count(u)) {
            if (degree2.count(w)&°ree2.count(v)) getValue(Expression(0,degree[u]),degree2[v],degree2[w]);
            else if (degree2.count(w)) AngleEquation(v,degree2[w]-Expression(0,degree[u]));
            else if (degree2.count(v)) AngleEquation(w,degree2[v]+Expression(0,degree[u]));
            continue;
        }
        if (degree.count(v)) {
            if (degree2.count(w)&°ree2.count(u)) getValue(degree2[u],Expression(0,degree[v]),degree2[w]);
            else if (degree2.count(w)) AngleEquation(u,degree2[w]-Expression(0,degree[v]));
            else if (degree2.count(u)) AngleEquation(w,degree2[u]+Expression(0,degree[v]));
            continue;
        }
        if (degree.count(w)) {
            if (degree2.count(u)&°ree2.count(v)) getValue(degree2[u],degree2[v],Expression(0,degree[w]));
            else if (degree2.count(u)) AngleEquation(v,Expression(0,degree[w])-degree2[u]);
            else if (degree2.count(v)) AngleEquation(u,Expression(0,degree[w])-degree2[v]);
            continue;
        }
        if (degree2.count(u)&°ree2.count(v)&°ree2.count(w)) {
            getValue(degree2[u],degree2[v],degree2[w]);
            continue;
        }
        if (degree2.count(u)&°ree2.count(v)) {
            AngleEquation(w,degree2[u]+degree2[v]);
            continue;
        }
        if (degree2.count(u)&°ree2.count(w)) {
            AngleEquation(v,degree2[w]-degree2[u]);
            continue;
        }
        if (degree2.count(v)&°ree2.count(w)) {
            AngleEquation(u,degree2[w]-degree2[v]);
            continue;
        }
    }
    for (auto &e:Base_Angle_Equation[3]) {
        auto u = sourceAngle[e.var1], v = sourceAngle[e.var2], w = sourceAngle[e.var3];
        u = sourceAngle[Find(Angle_fa,CreateAngle(u))];
        v = sourceAngle[Find(Angle_fa,CreateAngle(v))];
        w = sourceAngle[Find(Angle_fa,CreateAngle(w))];
        if (isEqual(u,v)&&isEqual(u,w)) {
            AngleEquation(u,60);
            AngleEquation(v,60);
            AngleEquation(w,60);
            continue;
        }
        if (degree.count(u)&°ree.count(v)) {
            AngleEquation(w,180-degree[u]-degree[v]);
            continue;
        }
        if (degree.count(u)&°ree.count(w)) {
            AngleEquation(v,180-degree[u]-degree[w]);
            continue;
        }
        if (degree.count(w)&°ree.count(v)) {
            AngleEquation(u,180-degree[v]-degree[w]);
            continue;
        }
        if (degree.count(u)) {
            if (degree2.count(w)&°ree2.count(v)) getValue(degree2[v],degree2[w],Expression(0,180-degree[u]));
            else if (degree2.count(w)) AngleEquation(v,Expression(0,180-degree[u])-degree2[w]);
            else if (degree2.count(v)) AngleEquation(w,Expression(0,180-degree[u])-degree2[v]);
            continue;
        }
        if (degree.count(v)) {
            if (degree2.count(w)&°ree2.count(u)) getValue(degree2[u],degree2[w],Expression(0,180-degree[v]));
            else if (degree2.count(w)) AngleEquation(u,Expression(0,180-degree[v])-degree2[w]);
            else if (degree2.count(u)) AngleEquation(w,Expression(0,180-degree[u])-degree2[u]);
            continue;
        }
        if (degree.count(w)) {
            if (degree2.count(u)&°ree2.count(v)) getValue(degree2[u],degree2[v],Expression(0,180-degree[w]));
            else if (degree2.count(u)) AngleEquation(v,Expression(0,180-degree[w])-degree2[u]);
            else if (degree2.count(v)) AngleEquation(u,Expression(0,180-degree[w])-degree2[v]);
            continue;
        }
        if (degree2.count(u)&°ree2.count(v)&°ree2.count(w)) {
            getValue(degree2[u]+degree2[v],degree2[w],Expression(0,180));
            continue;
        }
        if (degree2.count(u)&°ree2.count(v)) {
            AngleEquation(w,Expression(0,180)-degree2[u]-degree2[v]);
            continue;
        }
        if (degree2.count(u)&°ree2.count(w)) {
            AngleEquation(v,Expression(0,180)-degree2[u]-degree2[w]);
            continue;
        }
        if (degree2.count(v)&°ree2.count(w)) {
            AngleEquation(u,Expression(0,180)-degree2[v]-degree2[w]);
            continue;
        }
    }
    REP(i,1,tot) {
        Angle u = sourceAngle[Find(Angle_fa,i)];
        if (degree.count(u)) degree[sourceAngle[i]]=degree[u];
        else if (degree2.count(u)) degree2[sourceAngle[i]]=degree2[u];
    }
}
void solveLine() {
    int tot = BaseLine.size();
    REP(i,1,tot) {
        Line u = sourceLine[Find(Line_fa,i)];
        if (length.count(u)) length[sourceLine[i]]=length[u];
        else if (length2.count(u)) length2[sourceLine[i]]=length2[u];
    }
    for (auto &e:Base_Line_Equation2) {
        auto u = e.first.first, v = e.first.second, w = e.second;
        u = sourceLine[Find(Line_fa,CreateLine(u))];
        v = sourceLine[Find(Line_fa,CreateLine(v))];
        w = sourceLine[Find(Line_fa,CreateLine(w))];
        if (length.count(u)&&length.count(v)) {
            LineEquation(w,length[u]+length[v]);
            continue;
        }
        if (length.count(u)&&length.count(w)) {
            LineEquation(v,length[w]-length[u]);
            continue;
        }
        if (length.count(v)&&length.count(w)) {
            LineEquation(u,length[w]-length[v]);
            continue;
        }
        if (length.count(u)) {
            if (length2.count(w)&&length2.count(v)) getValue(Expression(0,length[u]),length2[v],length2[w]);
            else if (length2.count(w)) LineEquation(v,length2[w]-Expression(0,length[u]));
            else if (length2.count(v)) LineEquation(w,length2[v]+Expression(0,length[u]));
            continue;
        }
        if (length.count(v)) {
            if (length2.count(w)&&length2.count(u)) getValue(length2[u],Expression(0,length[v]),length2[w]);
            else if (length2.count(w)) LineEquation(u,length2[w]-Expression(0,length[v]));
            else if (length2.count(u)) LineEquation(w,length2[u]-Expression(0,length[v]));
            continue;
        }
        if (length.count(w)) {
            if (length2.count(u)&&length2.count(v)) getValue(length2[u],length2[v],Expression(0,length[w]));
            else if (length2.count(u)) LineEquation(v,Expression(0,length[w])-length2[u]);
            else if (length2.count(v)) LineEquation(u,Expression(0,length[w])-length2[v]);
            continue;
        }
        if (length2.count(u)&&length2.count(v)&&length2.count(w)) {
            getValue(length2[u],length2[v],length2[w]);
            continue;
        }
        if (length2.count(u)&&length2.count(v)) {
            LineEquation(w,length2[u]+length2[v]);
            continue;
        }
        if (length2.count(u)&&length2.count(w)) {
            LineEquation(v,length2[w]-length2[u]);
            continue;
        }
        if (length2.count(v)&&length2.count(w)) {
            LineEquation(u,length2[w]-length2[v]);
            continue;
        }
    }
    for (auto &e:Base_Line_Equation4) {
        auto a=e.first.first.first,b=e.first.first.second,c=e.first.second,d=e.second;
        //a/b=c/d
        solveProportional(a,b,c,d);
        pair u(a,b), v(c,d);
        if (u.second=1.5e8) continue;
        if (va.y==1e8) {
            if (vc.x*vc.x==vb.x*vb.x&&vc.x*vc.y==vb.x*vb.y) {
                int u = sqrt(vc.y*vc.y-vb.y*vb.y);
                if (u*u+vb.y*vb.y==vc.y*vc.y) LineEquation(a,u);
            }
            continue;
        }
        if (vb.y==1e8) {
            if (vc.x*vc.x==va.x*va.x&&vc.x*vc.y==va.x*va.y) {
                int u = sqrt(vc.y*vc.y-va.y*va.y);
                if (u*u+va.y*va.y==vc.y*vc.y) LineEquation(b,u);
            }
            continue;
        }
        if (vc.y==1e8) {
            //(a.xX+a.y)^2+(b.xX+b.y)^2
            if (va.x==0&&vb.x==0) {
                int u = sqrt(va.y*va.y+vb.y*vb.y);
                if (va.y*va.y+vb.y*vb.y==u*u) LineEquation(c,u);
            }
            continue;
        }
        //(a.xX+a.y)^2+(b.xX+b.y)^2=(c.xX+c.y)^2
        //(a.x^2+b.x^2-c.x^2) X^2 + (2a.x*a.y+2b.x*b.y-2c.x*c.y) X +a.y^2+b.y^2-c.y^2 = 0
        getValue(va.x*va.x+vb.x*vb.x-vc.x*vc.x,2*va.x*va.y+2*vb.x*vb.y-2*vc.x*vc.y,va.y*va.y+vb.y*vb.y-vc.y*vc.y);
    }
    REP(i,1,tot) {
        Line u = sourceLine[Find(Line_fa,i)];
        if (length.count(u)) length[sourceLine[i]]=length[u];
        else if (length2.count(u)) length2[sourceLine[i]]=length2[u];
    }
}
void solve() {
    solveAngle();
    solveLine();
    int cnt = BaseTriangle.size();
    REP(i,1,cnt) {
        auto &t = sourceTriangle[i];
        //等角对等边
        Angle xyz(t.x,t.y,t.z);
        Angle yzx(t.y,t.z,t.x);
        Angle zxy(t.z,t.x,t.y);
        Line xy(t.x,t.y),yz(t.y,t.z),zx(t.z,t.x);
        if (isEqual(xyz,yzx)) LineEquation(xy,zx);
        if (isEqual(xy,zx)) AngleEquation(xyz,yzx);
        if (isEqual(xyz,zxy)) LineEquation(zx,yz);
        if (isEqual(zx,yz)) AngleEquation(xyz,zxy);
        if (isEqual(zxy,yzx)) LineEquation(xy,yz);
        if (isEqual(xy,yz)) AngleEquation(zxy,yzx);
        //勾股定理
        if (isEqual(xyz,90)) ThePythagoreanTheorem(xy,yz,zx);
        if (isEqual(yzx,90)) ThePythagoreanTheorem(zx,yz,xy);
        if (isEqual(zxy,90)) ThePythagoreanTheorem(xy,zx,yz);
        REP(j,i+1,cnt) {
            auto &tt = sourceTriangle[j];
            //相似和全等
            TrianglesTheorem(t,tt);
        }
    }
}
int check() {
    if (Question.type==1) {
        if (length.count(Question.l)) {
            printf("%d\n", length[Question.l]);
            return 1;
        }
    }
    if (Question.type==2) {
        if (degree.count(Question.ang)) {
            printf("%d\n", degree[Question.ang]);
            return 1;
        }
    }
    if (Question.type==3) {
        if (Value!=1e8) {
            printf("%d\n", Value*Question.val.x+Question.val.y);
            return 1;
        }
    }
    return 0;
}
   
void work() {
    REP(i,1,5555-1) Line_fa[i]=Angle_fa[i]=i;
    BasePoint.clear();
    BaseLine.clear();
    length.clear();
    length2.clear();
    parallel.clear();
    perpendicular.clear();
    Point_Line.clear();
    degree.clear();
    degree2.clear();
    BaseAngle.clear();
    BaseTriangle.clear();
    Point_Circle.clear();
    for (auto &t:Base_Line_Equation) t.clear();
    for (auto &t:Base_Angle_Equation) t.clear();
    Value = 1e8;
    Base_Line_Equation2.clear();
    Base_Line_Equation3.clear();
    Base_Line_Equation4.clear();
    Base_Angle_Equation2.clear();
    Base_Angle_Equation3.clear();
    Base_Angle_Equation4.clear();
    string s;
    int n;
    cin>>n;
    cin.ignore();
    getline(cin,s);
    stringstream ss;
    ss<>s) CreatePoint(s[0]);
    getline(cin,s);
    stringstream ss2;
    ss2<>s) CreateLine(Line(s[0],s[1]));
    REP(i,1,n) {
        getline(cin,s);
        dfs(s,0,s.size()-1);
    }
    int cnt = BasePoint.size();
    //构造角
    REP(i,0,cnt-1) REP(j,0,cnt-1) REP(k,0,cnt-1) if (i!=j&&i!=k&&j!=k) {
        if (isCollinear(BasePoint[i],BasePoint[j],BasePoint[k])) continue;
        Line AB(BasePoint[i],BasePoint[j]);
        Line AC(BasePoint[i],BasePoint[k]);
        Line BC(BasePoint[j],BasePoint[j]);
        if (isExist(AB)&&isExist(AC)&&!isExist(BC,BasePoint[i])) {
            CreateAngle(Angle(BasePoint[j],BasePoint[i],BasePoint[k]));
        }
    }
    cnt = BaseAngle.size();
    REP(i,1,cnt) REP(j,i+1,cnt) {
        Angle a = sourceAngle[i];
        Angle b = sourceAngle[j];
        if (a.y==b.y) {
            //重合的角
            if ((isExist(Line(a.x,a.y),b.x)||isExist(Line(b.x,a.y),a.x))&&(isExist(Line(a.z,a.y),b.z)||isExist(Line(b.z,a.y),a.z))) {
                AngleEquation(a,b);
            }
            else if ((isExist(Line(a.x,a.y),b.z)||isExist(Line(b.z,a.y),a.x))&&(isExist(Line(a.z,a.y),b.x)||isExist(Line(b.x,a.y),a.z))) {
                AngleEquation(a,b);
            }
        }
    }
    cnt = BasePoint.size();
    REP(i,0,cnt-1) REP(j,0,cnt-1) if (i!=j) {
        REP(x,0,cnt-1) REP(y,0,cnt-1) if (i!=x&&i!=y&&j!=x&&j!=y&&x!=y) {
            Angle a(BasePoint[j],BasePoint[i],BasePoint[x]);
            Angle b(BasePoint[j],BasePoint[i],BasePoint[y]);
            Angle c(BasePoint[x],BasePoint[i],BasePoint[y]);
            //if (isExist(a)&&isExist(b)&&isExist(c)) AngleEquation(a,b,c);
        }
    }
    //构造三角形
    REP(i,0,cnt-1) REP(j,0,cnt-1) REP(k,0,cnt-1) if (i!=j&&i!=k&&j!=k) {
        if (isCollinear(BasePoint[i],BasePoint[j],BasePoint[k])) continue;
        Line AB(BasePoint[i],BasePoint[j]);
        Line BC(BasePoint[j],BasePoint[k]);
        Line CA(BasePoint[k],BasePoint[i]);
        if (isExist(AB)&&isExist(BC)&&isExist(CA)) {
            CreateTriangle(Triangle(BasePoint[i],BasePoint[j],BasePoint[k]));
        }
    }
    cnt = BaseTriangle.size();
    REP(i,1,cnt) {
        Triangle t = sourceTriangle[i];
        Angle xyz(t.x,t.y,t.z);
        Angle yzx(t.y,t.z,t.x);
        Angle zxy(t.z,t.x,t.y);
        AngleEquation2(xyz,yzx,zxy);
    }
    for (auto &t:Point_Circle) {
        for (int i=1; i diameter;
        for (int i=0; i>t;
    while (t--) work();
}