UVALive 6489 Triangles LA 6489 Triangles

UVALive 6489 Triangles LA 6489 Triangles"/>

UVALive 6489 Triangles LA 6489 Triangles

题目链接：.php?option=com_onlinejudge&Itemid=8&category=625&page=show_problem&problem=4500

详细题解：这丫的题目坑了我一个月，然后A了之后觉得自己的方法完全是个错的0.0

一开始的想法是：最大三角形面积很简单就是用凸包+旋转卡壳  ，最小三角形面积就是将每一个点极角排序。 然后求极点和每个相邻的两点组成的三角形的面积   之后发现这样有问题 如果这两边的夹角很大 但是长度很短  还是可能会面积最小 。 所以又想到以每个点为顶点，和其余点的用长度来排了下序，然后以长度的顺序来组成三角形之后发现这样测完所有数据要50s+

之后左搞右搞，发现原来极角排序写错了，干脆就删除了极角排序，然后发现还是超时30s+

然后无奈的乱改，把边排序的叉积的方法去掉，改为直接公式计算就9s了， 不曾想这竟然过了……

感觉完全就是逻辑错误，贴上代码，大家有什么正解的话，求在下面留言指教。。。。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 2100
#define inf 0x7fffffff
const double eps = 1e-8;
int dcmp(double x)
{if(fabs(x) < eps) return 0;else return x < 0 ? -1 : 1;
}
struct Point
{double x, y;Point(double x = 0, double y = 0) : x(x), y(y) {}};
Point p[N];
Point pp[N];
Point ch[N];
typedef Point Vector;Vector operator - (Point A, Point B) {return Vector(A.x-B.x, A.y-B.y);}
bool operator == (const Point &a, const Point &b){return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;}
bool operator != (const Point &a, const Point &b){return dcmp(a.x-b.x) != 0 || dcmp(a.y-b.y) != 0;}
double Dot(Vector A, Vector B){return A.x*B.x + A.y*B.y;}
double Length(Vector A){return sqrt(Dot(A, A));}
double Cross(Vector A, Vector B){return A.x*B.y - A.y*B.x;}
double Area2(Point A, Point B, Point C){return fabs(Cross(B-A, C-A));}Point tmp;
bool cmp_bian(Point a, Point b)
{double lena = (a.x-tmp.x)*(a.x-tmp.x)+(a.y-tmp.y)*(a.y-tmp.y);double lenb = (b.x-tmp.x)*(b.x-tmp.x)+(b.y-tmp.y)*(b.y-tmp.y);return dcmp(lena - lenb)< 0;//return Length(a - tmp) < Length(b-tmp);
}
bool cmp ( Point a, Point b )
{if ( a.x != b.x ) return a.x < b.x;else return a.y < b.y;
}//凸包
int ConvexHull(Point *p, int n, Point * ch)
{sort(p, p+n, cmp);int m = 0;for(int i = 0; i < n; i++){while(m > 1 && dcmp(Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) <= 0) m--;ch[m++] = p[i];}int k = m;for(int i = n-2; i >= 0; i--){while(m > k && dcmp(Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) <= 0) m--;ch[m++] = p[i];}if(n > 1) m--;return m;
}
//旋转卡壳求最大三角形面积
double rotaing_calipers(Point ch[], int n)
{int p;int i, j;double ans = 0;for( i = 0; i < n-1; i++){p = 1;for( j = i+1; j < n; j++){while(fabs(Cross(ch[j]-ch[i],ch[p+1]-ch[i])) > fabs((Cross(ch[j]-ch[i],ch[p]-ch[i]))))p = (p+1) % (n-1);ans = max(ans, fabs(Cross(ch[i]-ch[p],ch[j]-ch[p])));}ans = max(ans, fabs(Cross(ch[i]-ch[p],ch[j]-ch[p])));}return ans/2;
}
int main ()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int n;while(scanf("%d", &n),n){for(int i = 0; i < n; i++){scanf("%lf %lf", &p[i].x, &p[i].y);pp[i].x = p[i].x;pp[i].y = p[i].y;}double Min = inf, Max = -1;for(int i = 0; i < n; i++){tmp.x = p[i].x, tmp.y = p[i].y;double temp ;for(int j = 0; j < n; j++){if(p[i] == pp[j]) continue;if(pp[j+1] != p[i] && j+1 < n)temp = Area2(p[i], pp[j], pp[j+1])/2;else if(pp[j+1] == p[i] && j+2 < n)temp = Area2(p[i], pp[j], pp[j+2])/2;Min = min(Min, temp);if(Min == 0) break;}sort(pp, pp+n, cmp_bian);for(int j = 1; j < n-1; j++){temp = Area2(p[i],pp[j],pp[j+1])/2;Min = min(Min, temp);}if(Min == 0) break;}int len = ConvexHull(p, n, ch);Max = rotaing_calipers(ch, len);printf("%.1lf %.1lf\n", Min, Max);}return 0;
}