sdut 2831 Euclid (几何)

题目：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2831

题意：给a, b, c, d, e, f 6个点

abgh是平行四边形。def是三角形。面积相等。

求点 g, h的坐标

思路：

1. DE*DF/2 = AH*AB; （向量DE叉乘向量DF,除以2，等于向量AH叉乘 AB）

2. AH = k AC; (向量AH 等于 k倍的向量AC)

将2式代入1式。就可以求得。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <algorithm>
 7 using namespace std;
 8 
 9 struct point
10 {
11     double x, y;
12 }a, b, c, d, e, f, g, h;
13 double cross(point a, point b, point c)
14 {
15     return (fabs((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)));
16 }
17 int main()
18 {
19     double k;
20     while(cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y>>e.x>>e.y>>f.x>>f.y)
21     {
22         if(a.x==0&&a.y==0&&b.x==0&&b.y==0&&c.x==0&&c.y==0&&d.x==0&&d.y==0&&e.x==0&&e.y==0&&f.x==0&&f.y==0)
23             break;
24         k = cross(d, e, f)/2;
25         k = k/cross(a, b, c);
26 
27         h.x = a.x+k*(c.x-a.x);
28         h.y = a.y+k*(c.y-a.y);
29         g.x = b.x+(h.x-a.x);
30         g.y = b.y+(h.y-a.y);
31         printf("%.3lf %.3lf %.3lf %.3lf
", g.x, g.y, h.x, h.y);
32     }
33     return 0;
34 }
35

再贴一个比赛时候的代码。

思想是求的直线ac的方程，然后h满足方程，把h.y用h.x 代替。带入条件。

这样做有三个缺点： 1、把h.x带入方程，由于先要换成向量的坐标表示，还有相乘的部分和替换的部分，推导的过程很复杂。

2、算平行四边形的时候，不知道叉积出来到是正还是负，带入方程，会错。

3、方程斜率不存在的时候，要另算，麻烦。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <algorithm>
 7 using namespace std;
 8 
 9 struct node
10 {
11     double x, y;
12 } a, b, c, d, e, f, g, h;
13 double  area(node d, node e, node f)
14 {
15     return (fabs((e.x-d.x)*(f.y-d.y)-(e.y-d.y)*(f.x-d.x))/2);
16 }
17 int main()
18 {
19     double s_def;
20     while(cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y>>e.x>>e.y>>f.x>>f.y)
21     {
22         if(a.x==0&&a.y==0&&b.x==0&&b.y==0&&c.x==0&&c.y==0&&d.x==0&&d.y==0&&e.x==0&&e.y==0&&f.x==0&&f.y==0)
23             break;
24         s_def = area(d, e, f);
25 
26         double k , B;
27         if(a.x-c.x!=0)
28         {
29             k = (double)((a.y-c.y)/(a.x-c.x));
30             B = (double)(a.y-k*a.x);
31             cout<<k<<"  "<<B<<endl;
32             h.x = (double)((s_def+a.x*b.y+B*b.x-B*a.x-a.y*b.x)/(b.y-a.y-k*b.x+k*a.x));
33 
34             cout<<h.x<<endl;
35             h.y = k*h.x+B;
36         }
37         else
38         {
39             h.x = a.x;
40             double ab;
41             ab = sqrt((b.x-a.x)*(b.x-a.x)-(b.y-a.y)*(b.y-a.y));
42             h.y = a.y + s_def/ab;
43         }
44         g.x = b.x + h.x - a.x;
45         g.y = b.y + h.y - a.y;
46         printf("%.3lf %.3lf %.3lf %.3lf
", g.x, g.y, h.x, h.y);
47     }
48     return 0;
49 }