给出n个点，要你找到一个三角形，它的高是最长的。
思路：暴力超时了，是用先找出n个点与其他点的最长边，再枚举顶点过的.......具体证明不知道.....
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85 |
#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>using
namespace std;#define eps 1e-8struct
point{ double
x; double
y;};//点到直线的最短距离//bool vist[500][500][500];point intersection(point u1,point u2,point v1,point v2){ point ret=u1; double
t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x)); ret.x+=(u2.x-u1.x)*t; ret.y+=(u2.y-u1.y)*t; return
ret;}point ptoline(point p,point l1,point l2){ point t=p; t.x+=l1.y-l2.y; t.y+=l2.x-l1.x; return
intersection(p,t,l1,l2);}double
juli(point a,point b){ return
(sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));}<br>double
str[505][2];int
main(){ int
n; while(scanf("%d",&n)>0) { //memset(vist,false,sizeof(vist)); for(int
i=0; i<n; i++) scanf("%lf%lf",&str[i][0],&str[i][1]); double
maxn=0; point a,b,c; point sp[1000][2]; int
cnt=0; for(int
i=0; i<n; i++) { a.x=str[i][0]; a.y=str[i][1]; double
zd=0; for(int
j=0; j<n; j++) { if(i==j) continue; b.x=str[j][0]; b.y=str[j][1]; double
tmp=juli(a,b); if(tmp>zd) { zd=tmp; sp[cnt][0]=a; sp[cnt][1]=b; } } cnt++; } for(int
i=0; i<n; i++) { a.x=str[i][0]; a.y=str[i][1]; for(int
j=0; j<cnt; j++) { b=sp[j][0]; c=sp[j][1]; point d=ptoline(a,b,c); maxn=max(maxn,juli(d,a)); d=ptoline(b,a,c); maxn=max(maxn,juli(d,b)); d=ptoline(c,a,b); maxn=max(maxn,juli(d,c)); } } printf("%.5lf\n",maxn); } return
0;} |
zoj 3762（求三角形的最大高）,布布扣,bubuko.com
原文：http://www.cnblogs.com/ziyi--caolu/p/3581352.html