首页 > 代码库 > POJ 1927 Area in Triangle(计算几何)

POJ 1927 Area in Triangle(计算几何)

Area in Triangle


博客原文地址:http://blog.csdn.net/xuechelingxiao/article/details/40707691


题目大意:

给你一个三角形的三边边长,给你一跟绳子的长度,将绳子放在三角形里围起来的面积最大是多少。


解题思路:

当然可以想到当绳子的长度十分长的时候,绳子能围城的最大面积就是三角形的面积。

当然还可以想到的是当绳子的长度比较短,小于三角形的内接圆的长度时,绳子能围城的面积就是绳子能围成的圆的面积。

那么剩下要计算的就是当绳子长度小于三角形周长并且大于三角形内接圆的时候。

这种情况下,显然会是如图所示的情况。



那么这种情况下的面积怎么计算呢?

如图:



两个三角形是相似的,所以红色绳子所围成部分的面积就是大三角形的面积减去小三角形的的面积再加上小三角形内切圆的面积,也就是代码中

ans = S-S*t*t+Pi*rr*rr; 的意义,至于小三角形内切圆的半径,则是用小三角形与大三角形相似算出来的比例求得的。

我感觉说的挺详细的,具体的看代码吧。

#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <algorithm>
#define LL long long
//#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define max3(a, b, c) (a>b?max(a, c):max(b, c))
#define min3(a, b, c) (a<b?min(a, c):min(b, c))
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define min4(a, b, c, d) min(min(a, b), min(c, d))
#define Read()  freopen("data.in", "r", stdin);
#define Write() freopen("data.out", "w", stdout);

const double Pi = acos(-1.0);;
const double Ee = 2.718281828459045235360;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const double eps = 1e-8;
const int MOD = 1000000009;

const int dx4[] = {-1, 0, 1,  0};
const int dy4[] = { 0, 1, 0, -1};
const int dx8[] = {-1, 0, 1,  0, -1, -1,  1, 1};
const int dy8[] = {0 , 1, 0, -1, -1,  1, -1, 1};
const int dxhorse[] = {-2, -2, -1, -1, 1,  1, 2,  2};
const int dyhorse[] = {1 , -1,  2, -2, 2, -2, 1, -1};

using namespace std;

struct Point {
    double x, y;
} P[20010], m;

int dcmp(double x) {
    return x < -eps ? -1 : x > eps;
}

int main()
{
    double a, b, c, d;
    int icase = 1;
    while(~scanf("%lf%lf%lf%lf", &a, &b, &c, &d)) {
        if(dcmp(a)==0 && dcmp(b)==0 && dcmp(c)==0 && dcmp(d)==0) {
            break;
        }
        double L = a+b+c;
        double cosA = (b*b+c*c-a*a)/(2*b*c);
        double S = 0.5*b*c*(sqrt(1-cosA*cosA));
        double r = S*2/L;
        double ans;
        if(d > L) {
            ans = S;
        }
        else if(2*Pi*r >= d) {
            ans = d*d/(4*Pi);
        }
        else {
            double t = (L-d)/(L-2*Pi*r);
            double rr = r*t;
            ans = S-S*t*t+Pi*rr*rr;
        }
        printf("Case %d: %.2lf\n", icase++, ans);
    }

    return 0;
}

/*test case*/
/*

*/


POJ 1927 Area in Triangle(计算几何)