直线的一般方程为F(x) = ax + by + c = 0。既然我们已经知道直线的两个点，假设为(x0,y0), (x1, y1)，那么可以得到a = y0 – y1, b = x1 – x0, c = x0y1 – x1y0。
因此我们可以将两条直线分别表示为
F0(x) = a0*x + b0*y + c0 = 0, F1(x) = a1*x + b1*y + c1 = 0
那么两条直线的交点应该满足
a0*x + b0*y +c0 = a1*x + b1*y + c1
由此可推出
x = (b0*c1 – b1*c0)/D
y = (a1*c0 – a0*c1)/D
D = a0*b1 – a1*b0， (D为0时，表示两直线重合)
二者实际上就是连立方程组F0(x) = a0*x + b0*y + c0 = 0, F1(x) = a1*x + b1*y + c1 = 0的叉积应用
i j k
a0 b0 c0
a1 b1 c1
[cpp] view plain copy print ? #include <iostream> #include <string> using namespace std; struct Point { double x; double y; }; struct Line { Point p1,p2; double a,b,c; }; void GetLinePara(Line &l) { l.a=l.p1.y-l.p2.y; l.b=l.p2.x-l.p1.x; l.c=l.p1.x*l.p2.y-l.p1.y*l.p2.x; } Point getCrossPoint(Line &l1,Line &l2) { GetLinePara(l1); GetLinePara(l2); double D=l1.a*l2.b-l2.a*l1.b; Point p; p.x=(l1.b*l2.c-l2.b*l1.c)/D; p.y=(l1.c*l2.a-l2.c*l1.a)/D; return p; } int main() { Line L1,L2; while(true) { cout<<"Line1:\n"<<"Point1.x: "; cin>>L1.p1.x; cout<<"Point1.y: "; cin>>L1.p1.y; cout<<"Line1:\n"<<"Point2.x: "; cin>>L1.p2.x; cout<<"Point2.y: "; cin>>L1.p2.y; cout<<"Line2:\n"<<"Point1.x: "; cin>>L2.p1.x; cout<<"Point1.y: "; cin>>L2.p1.y; cout<<"Line2:\n"<<"Point2.x: "; cin>>L2.p2.x; cout<<"Point2.y: "; cin>>L2.p2.y; cout<<endl; Point PointCross=getCrossPoint(L1,L2); cout<<"CrossPoint.x:"<<PointCross.x<<endl; cout<<"CrossPoint.y:"<<PointCross.y<<endl; cout<<endl; } }
ZOJ Problem Set - 1683
题目大意：
在1*1的正方形格子上给出每边的两个点，按顺序连接对边的点，求这样形成的一系列四边形中最大的面积。
思路：
1. 求交点
见函数GetCrossPoint (http://blog.csdn.NET/abcjennifer/article/details/7584628)
2. 求面积
四边形面积可由两个三角形面积相加而得，这里使用叉积，因为三角形的两个向量边叉乘的结果为其所形成的平行四边形面积，所以三角形面积为1/2×向量边1 x 向量边2
见函数GetArea()
Code:
[cpp] view plain copy print ? #include"iostream" #include"stdio.h" #include"math.h" using namespace std; #define N 40 int n; struct Point { double x; double y; } pset[N + 1][N + 1]; struct Line { void L(Point pp1, Point pp2) { p1 = pp1; p2 = pp2; } Point p1, p2; double a, b, c; } lineset[N][N]; void GetLinePara(Line *l) { l->a = l->p1.y - l->p2.y; l->b = l->p2.x - l->p1.x; l->c = l->p1.x * l->p2.y - l->p2.x * l->p1.y; } Point GetCrossPoint(Line *l1, Line *l2) { GetLinePara(l1); GetLinePara(l2); double D = l1->a * l2->b - l2->a * l1->b; Point p; p.x = (l1->b * l2->c - l2->b * l1->c) / D; p.y = (l1->c * l2->a - l2->c * l1->a) / D; return p; } double Xmult(Point a, Point b, Point c)//get vector ac and bc 计算两个二维向量叉积，两条边界向量 { return (c.x - a.x) * (c.y - b.y) - (c.y - a.y) * (c.x - b.x); } double GetArea(int i, int j) { double area1 = Xmult(pset[i][j], pset[i + 1][j], pset[i + 1][j + 1]) / 2; double area2 = Xmult(pset[i][j], pset[i][j + 1], pset[i + 1][j + 1]) / 2; return fabs(area1) + fabs(area2); } void Init_Points() { int i; for (i = 1; i <= n; i++) scanf("%lf", &pset[i][0].x), pset[i][0].y = 0; for (i = 1; i <= n; i++) scanf("%lf", &pset[i][n + 1].x), pset[i][n + 1].y = 1; for (i = 1; i <= n; i++) scanf("%lf", &pset[0][i].y), pset[0][i].x = 0; for (i = 1; i <= n; i++) scanf("%lf", &pset[n + 1][i].y), pset[n + 1][i].x = 1; pset[0][0].x = pset[0][0].y = 0; pset[n + 1][0].x = 1, pset[n + 1][0].y = 0; pset[0][n + 1].x = 0, pset[0][n + 1].y = 1; pset[n + 1][n + 1].x = pset[n + 1][n + 1].y = 1; } void Init_Lines() { int i, j; Line l1, l2; for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { l1.L(pset[i][0], pset[i][n + 1]); l2.L(pset[0][j], pset[n + 1][j]); pset[i][j] = GetCrossPoint(&l1, &l2); } } } int main() { int i, j; while (cin >> n&&n) { Init_Points(); Init_Lines(); double maxarea = 0; double area; for (i = 0; i < n + 1; i++) for (j = 0; j < n + 1; j++) { area = GetArea(i, j); maxarea = area > maxarea ? area : maxarea; } printf("%lf\n", maxarea); } }
