/* This solution requires no knowledge of geometry other than the slope-intercept form of a line, the distance formula, and the 1/2*B*H formula for the area of a triangle.*/ #include #include #include #include #include #include #include using namespace std; //"Infinity" value #define INF 1E+15 //A point with X and Y value typedef struct _Point { double x, y; } Point; //A line in slope-intercept form, y = m*x + b typedef struct _Line { //The slope, INF if the line is vertical double m; //The y-intercept - or the x-intercept if the line is vertical double b; } Line; //Find the distance between 2 points double getDistance(Point p1, Point p2) { return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y)); } // Get a line in slope-intercept form based on 1 point and the slope of the line. Line lineFromPointSlope(Point point, double slope) { Line line; line.m = slope; //if line is vertical if (slope == INF) { line.b = point.x; } else { //To find the intercept, solve y=mx+b to get b = y-mx. line.b = point.y - line.m * point.x; } return line; } // Get a line in slope-intercept form based on 2 points on the line. Line lineFromPoints(Point p1, Point p2) { //If line is vertical if (p1.x == p2.x) return lineFromPointSlope(p1, INF); else { //Slope = rise/run - that is, (change in Y)/(change in X) double slope = (p2.y - p1.y) / (p2.x - p1.x); return lineFromPointSlope(p1, slope); } } //Find the intersection between 2 non-parallel lines. Point findIntersection(Line line1, Line line2) { Point point; //Check if either line is vertical if (line1.m == INF) { point.x = line1.b; point.y = line2.m * point.x + line2.b; } else if (line2.m == INF) { point.x = line2.b; point.y = line1.m * point.x + line1.b; } else { //Formula: y = m1*x + b1 = m2*x + b2 //So, x = (b2 - b1) / (m1 - m2) point.x = (line2.b - line1.b) / (line1.m - line2.m); point.y = line1.m * point.x + line1.b; } return point; } // Find the area of a triangle given 3 points. Points p1 and p2 are the base. double getArea(Point p1, Point p2, Point p3) { Line base = lineFromPoints(p1, p2); //Get the slope of a line perpendicular to the base double perpSlope; if (base.m == INF) perpSlope = 0; else if (base.m == 0) perpSlope = INF; else perpSlope = -1/base.m; //Find a perpendicular line that goes through the 3rd point (the "altitude") Line perpLine = lineFromPointSlope(p3, perpSlope); /* The place where the base and the perpendicular line meet. Its distance from point p3 will be the height of the triangle.*/ Point intersection = findIntersection(base, perpLine); //Area = 1/2*B*H return 0.5 * getDistance(p1, p2) * getDistance(p3, intersection); } int main() { ifstream infile("levees.in"); ofstream outfile("levees.out"); while (true) { //Each pair will contain the area followed by the perimeter of a levee. vector >leveeData(4); Point points[4]; infile >> points[0].x >> points[0].y >> points[1].x >> points[1].y >> points[2].x >> points[2].y >> points[3].x >> points[3].y; if (!infile.good()) return 0; //Find the intersection of the diagonals Point intersection = findIntersection( lineFromPoints(points[0], points[2]), lineFromPoints(points[1], points[3])); //Find the perimeter of each triangle for (int i = 0; i < 4; i++) { Point p1 = points[i]; Point p2 = points[(i+1)%4]; //Add up the lengths of the 3 sides double perim = getDistance(p1, p2) + getDistance(p1, intersection) + getDistance(p2, intersection); //Round to 3 decimal places leveeData[i].second = floor(perim * 1000 + 0.5) / 1000; } //Find the area of each triangle for (int i = 0; i < 4; i++) { Point p1 = points[i]; Point p2 = points[(i+1)%4]; double area = getArea(p1, p2, intersection); //Round to 3 decimal places leveeData[i].first = floor(area * 1000 + 0.5) / 1000; } /* Sort the results. By default, std::pair values are sorted by the first value (here, the area) with ties broken by the second value (the perimeter), which is exactly what we want.*/ sort(leveeData.begin(), leveeData.end()); outfile << fixed << setprecision(3); for (int i = 3; i >= 0; i--) { outfile << leveeData[i].first << " " << leveeData[i].second; if (i != 0) outfile << " "; } outfile << endl; } return 0; }