給出n個點，要你找到一個三角形，它的高是最長的。

思路：暴力超時了，是用先找出n個點與其他點的最長邊，再枚舉頂點過的.......具體證明不知道.....

#include<algorithm> #include<cstdio> #include<cstring> #include<cmath> using namespace std; #define eps 1e-8 struct 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))); }
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（求三角形的最大高）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。