BACKJOON 2681 - Rancher's Gift

문제: https://www.acmicpc.net/problem/2681

문제

Rancher Joel has a tract of land in the shape of a convex quadrilateral that he wants to divide among his sons Al, Bob, Chas and Dave, who wish to continue ranching on their portions, and his daughter Emily, who wishes to grow vegetables on her portion.

The center of the tract is most suitable for vegetable farming so Joel decides to divide the land by drawing lines from each corner (A, B, C, D in counter clockwise order) to the center of an opposing side (respectively A', B', C' and D' ). Each son would receive one of the triangular sections and Emily would receive the central quadrilateral section. As shown in the figure, Al's tract is to be bounded by the line from A to B, the line from A to the midpoint of BC and the line from B to the midpoint of CD; Bob's tract is to be bounded by the line from B to C, the line from B to the midpoint of CD and the line from C to the midpoint of DA, and so on.

Your job is to write a program that will help Rancher Joel determine the area of each child's tract and the length of the fence he will have to put around Emily's parcel to keep her brothers' cows out of her crops.

For this problem, A will always be at (0, 0) and B will always be at (x, 0). Coordinates will be in rods (a rod is 16.5 feet). The returned areas should be in acres to 3 decimal places (an acre is 160 square rods) and the length of the fence should be in feet, rounded up to the next foot.

입력

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains of a decimal integer followed by five (5) space separated floating-point values. The first (integer) value is the data set number, N. The floating-point values are B.x, C.x, C.y, D.x and D.y in that order (where V.x indicates the x coordinate of V and V.y indicates the y coordinate of V). Recall that the y coordinate of B is always zero (0).

The supplied coordinates will always specify a valid convex quadrilateral.

출력

For each data set there is a single line of output. It contains the data set number, N, followed by a single space followed by five (5) space separated Itoating point values to three (3) decimal place accuracy, followed by a single space and a decimal integer. The floating-point values are the areas in acres of the properties of Al, Bob, Chas, Dave, and Emily respectively. The final integer is the length of fence in feet required to fence in Emily's property (rounded up to the next foot).

예제 입력 

3
200 250 150 -50 200
200 200 100 0 100
201.5 157.3 115.71 -44.2 115.71

예제 출력 

5600.000 8661.765 12075.000 8666.667 8746.569 387
4000.000 4000.000 4000.000 4000.000 4000.000 279
4663.113 4663.113 4663.113 4663.113 4663.113 300

힌트

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2011 Greater New York Programming Contest G번

• 문제를 번역한 사람: baekjoon

링크

• ACM-ICPC Live Archive
• HDU Online Judge

각 선분의 교점을 구하고 신발끈 공식으로 각 땅의 넓이를 구했습니다.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
 
using namespace std;
 
struct Pos
{
    double x, y;
    Pos() : x(0.0), y(0.0) {}
    Pos(double _x, double _y) : x(_x), y(_y) {}
};
 
double getDistance(const Pos& a, const Pos& b)
{
    return sqrt(pow(b.x - a.x, 2) + pow(b.y - a.y, 2));
}
 
double getSlopeBetweenPoints(const Pos& a, const Pos& b)
{
    return (b.y - a.y) / (b.x - a.x);
}
 
Pos getLineIntersect(const Pos& a, double aSlope, const Pos& b, double bSlope)
{
    Pos ret;
    ret.x = (aSlope * a.x - bSlope * b.x + b.y - a.y) / (aSlope - bSlope);
    ret.y = aSlope * (ret.x - a.x) + a.y;
    return ret;
}
 
Pos getLineIntersect(const Pos& a1, const Pos& a2, const Pos& b1, const Pos& b2)
{
    return getLineIntersect(a1, getSlopeBetweenPoints(a1, a2), b1, getSlopeBetweenPoints(b1, b2));
}
 
double getArea(const Pos& a, const Pos& b, const Pos& c)
{
    return 0.5 * abs(a.x * b.y + b.x * c.y + c.x * a.y - b.x * a.y - c.x * b.y - a.x * c.y);
}
double getArea(const Pos& a, const Pos& b, const Pos& c, const Pos& d)
{
    return 0.5 * abs(a.x * b.y + b.x * c.y + c.x * d.y + d.x * a.y - b.x * a.y - c.x * b.y - d.x * c.y - a.x * d.y);
}
 
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        Pos a, b, c, d, a_, b_, c_, d_;
        for (int j = 0; j < 5; j++)
        {
            double coordinate;
            cin >> coordinate;
            switch (j)
            {
            case 0:
                b.x = coordinate;
                break;
            case 1:
                c.x = coordinate;
                break;
            case 2:
                c.y = coordinate;
                break;
            case 3:
                d.x = coordinate;
                break;
            case 4:
                d.y = coordinate;
                break;
            }
        }
        a_.x = (b.x + c.x) / 2.0;
        a_.y = (b.y + c.y) / 2.0;
        b_.x = (c.x + d.x) / 2.0;
        b_.y = (c.y + d.y) / 2.0;
        c_.x = (d.x + a.x) / 2.0;
        c_.y = (d.y + a.y) / 2.0;
        d_.x = (a.x + b.x) / 2.0;
        d_.y = (a.y + b.y) / 2.0;
 
 
        Pos ab_ = getLineIntersect(a, a_, b, b_);
        Pos bc_ = getLineIntersect(b, b_, c, c_);
        Pos cd_ = getLineIntersect(c, c_, d, d_);
        Pos da_ = getLineIntersect(d, d_, a, a_);
 
        cout.precision(3);
        cout << fixed << getArea(a, b, ab_) << " ";
        cout << fixed << getArea(b, c, bc_) << " ";
        cout << fixed << getArea(c, d, cd_) << " ";
        cout << fixed << getArea(d, a, da_) << " ";
        cout << fixed << getArea(ab_, bc_, cd_, da_) << " ";
        cout << (int)ceil(getDistance(da_, ab_) + getDistance(ab_, bc_)
            + getDistance(bc_, cd_) + getDistance(cd_, da_)) << endl;
    }
 
    return 0;
}