Triangle
求最大三角形
旋转卡壳
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <cmath> 6 using namespace std; 7 const double eps = 1e-8; 8 const int inf = 0x3f3f3f3f; 9 const int maxn = 50010; 10 11 struct Point{ 12 double x, y; 13 Point(double x = 0, double y = 0): x(x), y(y){} 14 }; 15 typedef Point Vector; 16 17 Vector operator - (Point a, Point b) { 18 return Vector(a.x - b.x, a.y - b.y); 19 } 20 Vector operator + (Vector a, Vector b) { 21 return Vector(a.x + b.x, a.y + b.y); 22 } 23 Vector operator * (Vector a, double p) { 24 return Vector(a.x * p, a.y * p); 25 } 26 Vector operator / (Vector a, double p) { 27 return Vector(a.x / p, a.y / p); 28 } 29 bool operator < (Point a, Point b) { 30 return a.x < b.x || a.x == b.x && a.y < b.y; 31 } 32 int dcmp(double x) { 33 if(fabs(x) < eps) return 0; 34 return x < 0 ? -1 : 1; 35 } 36 37 bool operator == (Point a, Point b) { 38 return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; 39 } 40 double Dot(Vector a, Vector b) { 41 return a.x * b.x + a.y * b.y; 42 } 43 double Cross(Vector a, Vector b) { 44 return a.x * b.y - a.y * b.x; 45 } 46 double Length(Vector a) { 47 return sqrt(Dot(a, a)); 48 } 49 double Angle(Vector a) { 50 return atan2(a.y, a.x); 51 } 52 53 int ConvexHull(Point *p, int n, Point *ch) { 54 sort(p, p+n); 55 int m = 0; 56 for(int i = 0; i < n; i++){ 57 while(m > 1 && Cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) <= 0) m--; 58 ch[m++] = p[i]; 59 } 60 int k = m; 61 for(int i = n-2; i >= 0; i--){ 62 while(m > k && Cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) <= 0) m--; 63 ch[m++] = p[i]; 64 } 65 if(n > 1) m--; 66 return m; 67 } 68 Point p[maxn], ch[maxn]; 69 int vis[maxn]; 70 71 double RotateCalipers(Point *p, int n){ 72 if(n < 3) return 0; 73 p[n] = p[0]; 74 int i = 0, j = 1, k = 2; 75 int a, b, c; 76 double area = -inf; 77 memset(vis, 0, sizeof(vis)); 78 while(!vis[2]){ 79 a = i, b = j, c = k; 80 while(Cross(p[j] - p[i], p[k] - p[i]) < Cross(p[j] - p[i], p[k+1] - p[i])) k = (k+1) % n, vis[k] = 1; 81 while(Cross(p[j] - p[i], p[k] - p[i]) < Cross(p[j+1] - p[i], p[k] - p[i])) j = (j+1) % n; 82 while(Cross(p[j] - p[i], p[k] - p[i]) < Cross(p[j] - p[i+1], p[k] - p[i+1])) i = (i+1) % n; 83 area = max(area, Cross(p[j] - p[i], p[k] - p[i])); 84 if(a==i && b==j && c==k) { 85 k = (k+1)%n; 86 vis[k] = 1; 87 } 88 } 89 return area / 2; 90 } 91 92 int main(){ 93 //freopen("in.txt", "r", stdin); 94 int n; 95 while(scanf("%d", &n) && ~n){ 96 for(int i = 0; i < n; i++){ 97 scanf("%lf %lf", &p[i].x, &p[i].y); 98 } 99 int sz = ConvexHull(p, n , ch); 100 printf("%.2f ", RotateCalipers(ch, sz)); 101 } 102 return 0; 103 }