Language: C++
/*
14.7.8 Nice Milk
PC/UVa IDs: 111408/10117, Popularity: C, Success rate: low Level: 4
To build using Visucal Studio 2008:
cl -EHsc -O2 nice_milk.cpp
*/
/*
Do a backtrack.
For each iteration:
Starting with the original points of the polygon,
choose a pair of points k-times.
For each iteration with a pair of points p1, p2:
Get a directed dipped line that is on the left side of
a vector from p1 to p2.
The line has the same direction as the vector from p1 to p2.
Get the points that the dipped line intersects with other line
segments of the polygon,
and add them between the points in which the line intersects.
Iterate all of the points of the polygon and remove the points
that are on the right side of the line.
Calculate the area of polygon in which some points are replaced by
the above process, and
record the minimum area.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cfloat>
#include <cmath>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;
#define EPSILON FLT_EPSILON /* DBL_EPSILON */
const double pi = 2.0 * acos(0.0); // 3.14159265358979323846
struct point {
double x, y;
point() : x(0.0), y(0.0) {}
point(double _x, double _y) : x(_x), y(_y) {}
point(const point &p) : x(p.x), y(p.y) {}
bool operator==(const point& p) const
{return fabs(x - p.x) <= EPSILON && fabs(y - p.y) <= EPSILON;}
};
struct line {
double a; // x-coefficient
double b; // y-coefficient
double c; // constant term
};
struct line_segment {
point p1, p2;
line_segment(const point& _p1, const point& _p2) : p1(_p1), p2(_p2) {}
};
double signed_triangle_area(const point& a, const point& b, const point& c)
{
return (a.x * b.y - a.y * b.x + a.y * c.x -
a.x * c.y + b.x * c.y - c.x * b.y) / 2.0;
}
bool ccw(const point& a, const point& b, const point& c)
{
// see if the point c is to the left of a -> b
// (or, a - b - c are counterclockwise)
return signed_triangle_area(a, b, c) > EPSILON;
}
void points_to_line(const point& p1, const point& p2, line& l)
{
if (fabs(p1.x - p2.x) <= EPSILON) {
l.a = 1; l.b = 0; l.c = -p1.x;
}
else {
l.b = 1;
l.a = -(p1.y - p2.y)/(p1.x - p2.x);
l.c = -(l.a * p1.x) - l.b * p1.y;
}
}
bool parallelQ(const line& l1, const line& l2)
{
return fabs(l1.a - l2.a) <= EPSILON && fabs(l1.b - l2.b) <= EPSILON;
}
bool same_lineQ(const line& l1, const line& l2)
{
return parallelQ(l1, l2) && fabs(l1.c - l2.c) <= EPSILON;
}
bool point_in_box(const point& p, const point& b1, const point& b2)
{
return p.x >= min(b1.x, b2.x) - EPSILON && p.x <= max(b1.x, b2.x) + EPSILON &&
p.y >= min(b1.y, b2.y)- EPSILON && p.y <= max(b1.y, b2.y) + EPSILON;
}
bool intersection_point(const line& l1, const line& l2, point& p)
{
if (same_lineQ(l1, l2)) {
#ifdef DEBUG
printf("Warning: Identical lines, all points intersect.\n");
#endif
return false;
}
if (parallelQ(l1, l2)) {
#ifdef DEBUG
printf("Error: Distinct parallel lines do not intersect.\n");
#endif
return false;
}
p.x = (l2.b * l1.c - l1.b * l2.c) / (l2.a * l1.b - l1.a * l2.b);
if (fabs(l1.b) > EPSILON) // test for vertical line
p.y = - (l1.a * p.x + l1.c) / l1.b;
else
p.y = - (l2.a * p.x + l2.c) / l2.b;
return true;
}
bool line_segments_intersect(const line_segment& s, const line& l, point& p)
{
line ls;
points_to_line(s.p1, s.p2, ls);
if (same_lineQ(ls, l)) // overlapping or disjoint segments
return false;
if (parallelQ(ls, l))
return false;
intersection_point(ls, l, p);
return point_in_box(p, s.p1, s.p2);
}
double polygon_area(const vector<point>& polygon)
{
double area = 0.0;
for (int i = 0; i < polygon.size(); i++) {
int j = (i + 1) % polygon.size();
area += polygon[i].x * polygon[j].y - polygon[j].x * polygon[i].y;
}
return area / 2.0;
}
void get_dipped_line(int h, const point& p1, const point& p2,
point& dp1, point& dp2, line& dl)
{
// get the dipped points that are on the left side of the lines perpendicular
// to a vector from p1 to p2, and are distant from the vector by h
double angle = atan2(p2.y - p1.y, p2.x - p1.x);
dp1 = point(p1.x + h * cos(angle + pi / 2.0),
p1.y + h * sin(angle + pi / 2.0));
dp2 = point(p2.x + h * cos(angle + pi / 2.0),
p2.y + h * sin(angle + pi / 2.0));
points_to_line(dp1, dp2, dl);
}
void dip_bread(int h, int i, int j, const vector<point>& points,
const vector<point>& dpoints, vector<point>& result)
{
point dp1, dp2;
line dl;
get_dipped_line(h, points[i], points[j], dp1, dp2, dl);
for (int i = 0; i < dpoints.size(); i++) {
int j = (i + 1) % dpoints.size();
if (!ccw(dp1, dp2, dpoints[i]))
;
else
result.push_back(dpoints[i]);
line_segment ls(dpoints[i], dpoints[j]);
point dp;
if (line_segments_intersect(ls, dl, dp))
result.push_back(dp);
}
}
void cover_sides_of_bread_with_milk(int k, int l, int h,
const vector<point>& points,
vector<point>& dpoints, double& min_area)
{
if (min_area == 0.0)
return;
else if (dpoints.empty())
min_area = 0.0;
else if (!k) {
double area = polygon_area(dpoints);
if (area < min_area)
min_area = area;
}
else {
for (int i = l; i < points.size(); i++) {
int j = (i + 1) % points.size();
vector<point> result;
dip_bread(h, i, j, points, dpoints, result);
cover_sides_of_bread_with_milk(k - 1, i + 1, h, points, result, min_area);
}
}
}
int main(int /* argc */, char** /* argv */)
{
#ifdef __ELAPSED_TIME__
clock_t start = clock();
#endif
while (true) {
int n, k, h;
cin >> n >> k >> h;
if (!n && !k && !h)
break;
if (k > n)
k = n;
vector<point> points;
for (int i = 0; i < n; i++) {
point p;
cin >> p.x >> p.y;
points.push_back(p);
}
double area = polygon_area(points);
double min_area = DBL_MAX;
if (!h || !k)
min_area = area;
else {
vector<point> dpoints(points);
cover_sides_of_bread_with_milk(k, 0, h, points, dpoints, min_area);
}
printf("%.2f\n", area - min_area);
}
#ifdef __ELAPSED_TIME__
cerr << "elapsed time = " <<
static_cast<double>(clock() - start) / CLOCKS_PER_SEC << " sec.\n";
#endif
return 0;
}
No comments:
Post a Comment