UVa 1643 – Angle and Squares [几何]

点击打开vjudge题目链接

题意:在坐标系第一象限给一个定点在原点的角,然后给定n个正方形,问怎样在这个角里放正方形才使得左边阴影部分面积最大。

分析:画画图可以发现当这些正方形的对角线连成一条直线的时候阴影面积最大。然后推出公式即可。

下面代码可以作为模板使用(刚才做题又修复了多处bug…)

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-8;
inline int dcmp(double x) {
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}
struct Point{
    double x, y;
    Point():x(0), y(0){}
    Point(double x, double y):x(x), y(y){}
    Point(const Point & rhs):x(rhs.x), y(rhs.y){}
    Point operator + (Point rhs) const { return Point(x+rhs.x, y+rhs.y); }
    Point operator - (Point rhs) const { return Point(x-rhs.x, y-rhs.y); }
    Point operator * (double t) const { return Point(x*t, y*t); }
    bool operator < (const Point & rhs) const {
        return x < rhs.x || (x == rhs.x && y < rhs.y);
    }
    bool operator == (const Point & rhs) const {
        return !dcmp(x-rhs.x) && !dcmp(y-rhs.y);
    }
    double dot(Point rhs) { return x * rhs.x + y * rhs.y; }
    double cross(Point rhs) { return x * rhs.y - y * rhs.x; }
    double length() { return hypot(x, y); }
    double angle(Point rhs) { return acos(dot(rhs)/length()/rhs.length()); }
    Point rotateAngle(double rad) {
        return Point(x*cos(rad) - y*sin(rad), x*sin(rad) + y*cos(rad));
    }
};
typedef Point Vec;
typedef deque<Vec> Polygon;

double triArea(Point a, Point b, Point c) {
    return (b-a).cross(c-a)/2.0;
}
double cross(Vec lhs, Vec rhs) { return lhs.cross(rhs); }
double dot(Vec lhs, Vec rhs) { return lhs.dot(rhs); }

Point getLineInter(Point p, Vec v, Point q, Vec w) {
    Vec u = p - q;
    double t = cross(w, u) / cross(v, w);
    return p + v * t;
}
bool inSeg(Point p, Point a1, Point a2) {
    return dcmp(cross(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0;
}
bool onSeg(Point p, Point a1, Point a2) {
    return dcmp(cross(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) <= 0;
}
bool segProperInter(Point a1, Point a2, Point b1, Point b2) {
    double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
    double c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
    return dcmp(c1 * c2) < 0 && dcmp(c3 * c4) < 0;
}
bool segInter(Point a1, Point a2, Point b1, Point b2) {
    double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
    double c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
    return dcmp(c1 * c2) <= 0 && dcmp(c3 * c4) <= 0;
}

double polygonArea(const Polygon & p) {
    double area = 0;
    int sz = p.size();
    for (int i = 2; i < sz; ++i)
        area += triArea(p[0], p[i - 1], p[i]);
    return area / 2;
}
bool isProtrude(const Polygon & p) {
    Polygon v;
    int sz = p.size();
    for (int i = 0; i < sz; ++i)
        v.push_back(p[(i + 1) % sz] - p[i]);
    int flag = dcmp(cross(v[1], v[0]));
    for (int i = 0; i < sz; ++i)
        if (dcmp(cross(v[(i + 1) % sz], v[i])) != flag)
            return false;
    return true;
}
Polygon convexHull(Polygon p){
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    int i, n = p.size(), m = 0;
    Polygon ch(n + 1);
    for(i = 0; i < n; ++i){
        while(m >= 2 && dcmp(cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) <= 0) --m;
        ch[m++] = p[i];
    }
    int k = m;
    for(i = n - 2; i >= 0; --i){
        while(m > k && dcmp(cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) <= 0) --m;
        ch[m++] = p[i];
    }
    if(n > 1) --m; ch.resize(m);
    return ch;
}


//----------------------------------------------------------------------------------

int n;

int main() {
    ios::sync_with_stdio(false);
    while(cin >> n, n) {
        Vec a, b; cin >> a.x >> a.y >> b.x >> b.y;
        double len = 0, area = 0;
        for(int i = 0; i < n; ++i) {
            double x; cin >> x;
            len += x;
            area += x * x / 2;
        }
        double k1 = a.y / a.x, k2 = b.y / b.x;
        if(k1 > k2) swap(k1, k2);
        double x1 = len*(k2+1)/(k2-k1), y1 = k1*x1;
        double x2 = len*(k1+1)/(k2-k1), y2 = k2*x2;
        area = triArea(Point(0, 0), Point(x1, y1), Point(x2, y2)) - area;
        // area = Vec(x1, y1).cross(Vec(x2, y2)) / 2 - area;
        cout << fixed << setprecision(3) << area << endl;
    }
    return 0;
}

欢迎留言