Triangle

求最大三角形

旋转卡壳

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             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\n", RotateCalipers(ch, sz));101     }102     return 0;103 }