计算几何

题意

一片真心醉红尘，两处人间皆相印。

随着时间的推移，两人的感情越发深厚，心心相印，默契非凡。
但是，作为一个理科生，LFgg想要一个能够量化的模型，来测试两人的默契程度。
这天，LFgg请来了他的NPY，邀请她做一个测试。两人同时报出坐标系中的两点，过NPY的两点做一条线段，同时以LFgg报出的两点做一个矩形，看它们是否存在公共点。
矩形范围包括四条边及内部的所有点。
LFgg和NPY记录了很多次数据（多次测量减小误差），筋疲力尽的LFgg已经难以去判断是否有公共点了，所以他将这个问题交给了你。

Input
第一行包含一个整数n，代表数据组数。
接下来每一行包含八个整数 x_start,y_start,x_end,y_end,x_1,y_1,x_2,y_2。
(x_start,y_start)代表线段起点，(x_end,y_end)代表线段终点，(x_1,y_1)与(x_2,y_2)为矩形的两个对角点，唯一确定一个矩形。（边平行于x，y轴）

Output
对于每一行，若线段与矩形有公共点，则输出“T”否则输出“F”（没有括号）。

Sample Input
1
4 9 11 2 1 5 7 1
Sample Output
F

分析

题并不难、冷静的分析与思考是关键！！！
题目并不难理解，主要就是在一个直角坐标系中判断一个正方形面与一条线段是否有公共点。(含边界)

如何进行判断呢？
看图：

我们先看如果有i骄傲点的话会怎么样？比如:

和这样：

你会发现一个非常有意思的地方就是，在这两种情况，该线段一定会交矩形的其中一条对角线！！！！
这是个充要条件，如果该线段交矩形的其最终一条对角线，那么意味着该线段在矩形内和对角线有交点。

好了，到这我们其实已经将解决了大部分问题了。剩下的还有两种情况：


唯有这两种情况会打破上述规则，即都和对角线不相交但是却有公共点。
我们不难看出他的规律：即至少有一个端点在矩形内！

ok！这道题已经被我们分析完了。

剩下的问题的关键变为如何判断对角线是否和所给直线相交，即如何判断两线段相交？
利用高中的几何知识，给的两个点在一个在直线上一个在直线下那么这个直线就与这个线段相交。
我们对于两组点(x0,y0)、(x1,y2)。(x2,y2)、(x3,y3)。
即其所称的直线a1x+b1y+c1 = 0 、 a2x+b2y+c2 = 0
着两线段分别与对方的直线有交点。那么两直线只有一个交点，故两线段有交点。
即(a1x2+b1y2+c1) * (a1x3+b1y3+c1) <= 0
且(a2x0+b2y0+c2) * (a2x1+b2y1+c2) <= 0
至于，a,b,c如何求，参考高中知识

代码如下、注意细节

#include<iostream>
#include<algorithm>
using namespace std;
int n;

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    int a0, b0, c0;
    int a1, b1, c1;
    int a2, b2, c2;
    int xs, ys, xe, ye;
    int x0, y0, x1, y1;
    int x2, y2, x3, y3;
    for (int i = 0;i < n;i++) {
        cin >> xs >> ys >> xe >> ye;
        cin >> x0 >> y0 >> x1 >> y1;
        x2 = x0;y2 = y1;x3 = x1;y3 = y0;
        a0 = ys - ye;b0 = xe - xs;c0 = xs * ye - xe * ys;
        a1 = y0 - y1;b1 = x1 - x0;c1 = x0 * y1 - x1 * y0;
        a2 = y2 - y3;b2 = x3 - x2;c2 = x2 * y3 - x3 * y2;
        if ((a0 * x0 + b0 * y0 + c0) * (a0 * x1 + b0 * y1 + c0) <= 0 && (a1 * xs + b1 * ys + c1) * (a1 * xe + b1 * ye + c1) <= 0) {
            cout << "T" << endl;
        }
        else if ((a0 * x2 + b0 * y2 + c0) * (a0 * x3 + b0 * y3 + c0) <= 0 && (a2 * xs + b2 * ys + c2) * (a2 * xe + b2 * ye + c2) <= 0) {
            cout << "T" << endl;
        }
        else if (xs <= max(x0, x1) && xs >= min(x0, x1) && ys <= max(y0, y1) && ys >= min(y0, y1)) {
            cout << "T" << endl;
        }
        else if (xe <= max(x0, x1) && xe >= min(x0, x1) && ye <= max(y0, y1) && ye >= min(y0, y1)) {
            cout << "T" << endl;
        }
        else cout << "F" << endl;
    }
}

这次代码我觉得还是写的比较漂亮的，但是各种变量实在是太容易混了，再加上当时时间紧迫，因为打错而W了三次。。。。。。还是基本功不够扎实啊！！！！