HDU 6398 Pizza Hub（计算几何 三角形放置）

http://acm.hdu.edu.cn/showproblem.php?pid=6398

题意：

给一个可旋转的三角形，求一个宽为W的矩形的最小高度，使得这个三角形可以塞进去

解析：

一定有一个点在边上，所以枚举每个点P做（吉如一jls推荐的旋转平移流）

• 平移坐标系使得P落在原点
  

• 选择第二个点K，尝试这样放
  

• 如果不行，就这样放
  

• 或者这样
  

• 通过K的旋转，计算得到最后一个点K2的位置

  • 这里需要注意由于精度误差，两个夹角为180度的向量，acos内的部分可能是$-1.0000001$，这样acos的结果会是nan
    

• 用这三个点计算答案
  

代码：

/**  Author : Jk_Chen*    Date : 2021-03-27-13.51.34*/
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define rep(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)
#define per(i, a, b) for (int i = (int)(a); i >= (int)(b); i--)
#define mmm(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define pill pair<int, int>
#define fi first
#define se second
void test()
{cerr << "\n";
}
template <typename T, typename... Args>
void test(T x, Args... args)
{cerr << "> " << x << " ";test(args...);
}
const LL mod = 1e9 + 7;
const int maxn = 1e5 + 9;
const int inf = 0x3f3f3f3f;
LL rd()
{LL ans = 0;char last = ' ', ch = getchar();while (!(ch >= '0' && ch <= '9'))last = ch, ch = getchar();while (ch >= '0' && ch <= '9')ans = ans * 10 + ch - '0', ch = getchar();if (last == '-')ans = -ans;return ans;
}
#define rd rd()
/*_________________________________________________________begin*/
#define F double
F eps=1e-9;
const F pi=acos(-1);struct point{F x,y;point(){}point(F x,F y):x(x),y(y){}
};
typedef point Vector;
typedef point Point;
Vector operator + (Vector a, Vector b){//向量加法return Vector(a.x + b.x, a.y + b.y);
}
Vector operator - (Vector a, Vector b){//向量减法return Vector(a.x - b.x, a.y - b.y);
}
Vector operator * (Vector a, F p){//向量数乘return Vector(a.x*p, a.y*p);
}
Vector operator / (Vector a, F p){//向量数除return Vector(a.x / p, a.y / p);
}
int dcmp(F x){//精度三态函数(>0,<0,=0)if (fabs(x) < eps)return 0;else if (x > 0)return 1;return -1;
}
bool operator == (const Point &a, const Point &b){//向量相等return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}
F Dot(Vector a, Vector b){//内积return a.x*b.x + a.y*b.y;
}
F Length(Vector a){//模return sqrt(Dot(a, a));
}
F Cross(Vector a, Vector b){//外积return a.x*b.y - a.y*b.x;
}
F Angle(Vector a, Vector b)
{ //夹角,弧度制F d2 = Dot(a, b) / Length(a) / Length(b);if (d2 < -1)d2 = -1;if (d2 > 1)d2 = 1;F ang = acos(d2);if (Cross(a, b) < 0){ang = -ang;}return ang;
}
Vector Rotate(Vector a, F rad){//逆时针旋转return Vector(a.x*cos(rad) - a.y*sin(rad), a.x*sin(rad) + a.y*cos(rad));
}
Vector RotateTogether(Vector A1, Vector A2, Vector C){ //A1旋转到A2后，C应该旋转到哪里F ang = Angle(A1, A2);return Rotate(C, ang);
}
F Distance(Point a, Point b){//两点间距离return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
F Area(Point a, Point b, Point c){//三角形面积return fabs(Cross(b - a, c - a) / 2);
}
bool Intersect(Point a, Point b, Point c, Point d){//线段相交（不包括端点）F t1 = Cross(c - a, d - a)*Cross(c - b, d - b);F t2 = Cross(a - c, b - c)*Cross(a - d, b - d);return dcmp(t1) < 0 && dcmp(t2) < 0;
}
bool StrictIntersect(Point a, Point b, Point c, Point d){ //线段相交（包括端点）returndcmp(max(a.x, b.x) - min(c.x, d.x)) >= 0&& dcmp(max(c.x, d.x) - min(a.x, b.x)) >= 0&& dcmp(max(a.y, b.y) - min(c.y, d.y)) >= 0&& dcmp(max(c.y, d.y) - min(a.y, b.y)) >= 0&& dcmp(Cross(c - a, d - a)*Cross(c - b, d - b)) <= 0&& dcmp(Cross(a - c, b - c)*Cross(a - d, b - d)) <= 0;
}
F DistanceToLine(Point A, Point M, Point N){//点A到直线MN的距离,Error:MN=0return fabs(Cross(A - M, A - N) / Distance(M, N));
}
Point GetLineIntersection(Point P, Vector v, Point Q, Vector w){//两直线的交点Vector u = P - Q;F t = Cross(w, u) / Cross(v, w);return P + v * t;
}
void check(F &ans, point a[3], F m)
{F X = max(max(a[0].x, a[1].x), a[2].x) - min(min(a[0].x, a[1].x), a[2].x);F Y = max(max(a[0].y, a[1].y), a[2].y) - min(min(a[0].y, a[1].y), a[2].y);if (dcmp(X - m) <= 0){ans = min(ans, Y);}if (dcmp(Y - m) <= 0){ans = min(ans, X);}
}
F rdF()
{double x;scanf("%lf", &x);return (F)x;
}
void __()
{point a[3];point b[3];F ans = 1e18;rep(i, 0, 2)a[i].x = rdF(),a[i].y = rdF();F m = rdF();rep(i, 0, 2){int k = (i + 1) % 3;int k2 = (i + 2) % 3;rep(j, 0, 2)b[j] = a[j];rep(j, 0, 2){if (j != i)b[j] = b[j] - b[i];}b[i] = {0, 0};if (Length(b[k]) <= m){point bb = {Length(b[k]), 0};b[k2] = RotateTogether(b[k], bb, b[k2]);b[k] = bb;check(ans, b, m);}else{if (1){point bb = {m, sqrt(Length(b[k]) * Length(b[k]) - m * m)};b[k2] = RotateTogether(b[k], bb, b[k2]);b[k] = bb;check(ans, b, m);}if (1){rep(j, 0, 2)b[j] = a[j];rep(j, 0, 2){if (j != i)b[j] = b[j] - b[i];}b[i] = {0, 0};point bb = {m, -sqrt(Length(b[k]) * Length(b[k]) - m * m)};b[k2] = RotateTogether(b[k], bb, b[k2]);b[k] = bb;check(ans, b, m);}}}if (ans > 1e17){puts("impossible");}else{printf("%.10f\n", (double)ans);}
}int main()
{int t = rd;while (t--){__();}return 0;
}/*_________________________________________________________end*/