2015年百度之星初赛(1) --- F 矩形面积

简介: 矩形面积 Problem Description 小度熊有一个桌面,小度熊剪了很多矩形放在桌面上,小度熊想知道能把这些矩形包围起来的面积最小的矩形的面积是多少。   Input 第一行一个正整数 T,代表测试数据组数($1 \leq T \leq 20$),接下来 T 组测试数据。

矩形面积

Problem Description
小度熊有一个桌面,小度熊剪了很多矩形放在桌面上,小度熊想知道能把这些矩形包围起来的面积最小的矩形的面积是多少。
 
Input
第一行一个正整数 T,代表测试数据组数($1 \leq T \leq 20$),接下来 T 组测试数据。

每组测试数据占若干行,第一行一个正整数 $N(1 \leq N < \leq 1000)$,代表矩形的数量。接下来 N 行,每行 8 个整数$x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4$,代表矩形的四个点坐标,坐标绝对值不会超过10000。
 
Output
对于每组测试数据,输出两行:

第一行输出"Case #i:",i 代表第 i 组测试数据。
第二行包含1 个数字,代表面积最小的矩形的面积,结果保留到整数位。
 
Sample Input
2
2
5 10 5 8 3 10 3 8
8 8 8 6 7 8 7 6
1
0 0 2 2 2 0 0 2
 
Sample Output
Case #1:
17
Case #2:
4

Problem's Link:   http://acm.hdu.edu.cn/showproblem.php?pid=5251


 

Mean: 

 

analyse:

把n个矩形的点输入多边形寻找最小覆盖面积矩形的模版代码中就OK,网上套的模板。

Time complexity: O(n)

 

Source code: 

 

/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-05-31-23.18
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define  LL long long
#define  ULL unsigned long long
using namespace std;
const double eps = 1e-8;
const int N = 4004;
int sign(double d)
{
    return d < -eps ? -1 : (d > eps);
}
struct point
{
    double x, y;
    point operator-(point d){
        point dd;
        dd.x = this->x - d.x;
        dd.y = this->y - d.y;
        return dd;
    }
    point operator+(point d){
        point dd;
        dd.x = this->x + d.x;
        dd.y = this->y + d.y;
        return dd;
    }
    void read(){ scanf("%lf%lf", &x, &y); }
}ps[N];

int n, cn;

double dist(point d1, point d2)
{
    return sqrt(pow(d1.x - d2.x, 2.0) + pow(d1.y - d2.y, 2.0));
}

double dist2(point d1, point d2)
{
    return pow(d1.x - d2.x, 2.0) + pow(d1.y - d2.y, 2.0);
}

bool cmp(point d1, point d2)
{
    return d1.y < d2.y || (d1.y == d2.y && d1.x < d2.x);
}

//st1-->ed1叉乘st2-->ed2的值
double xmul(point st1, point ed1, point st2, point ed2)
{
    return (ed1.x - st1.x) * (ed2.y - st2.y) - (ed1.y - st1.y) * (ed2.x - st2.x);
}

double dmul(point st1, point ed1, point st2, point ed2)
{
    return (ed1.x - st1.x) * (ed2.x - st2.x) + (ed1.y - st1.y) * (ed2.y - st2.y);
}

//多边形类
struct poly
{
    static const int N = 50005; //点数的最大值
    point ps[N+5]; //逆时针存储多边形的点,[0,pn-1]存储点
    int pn;  //点数
    poly() { pn = 0; }
    //加进一个点
    void push(point tp)
    {
        ps[pn++] = tp;
    }
    //第k个位置
    int trim(int k)
    {
        return (k+pn)%pn;
    }
    void clear(){ pn = 0; }
};

//返回含有n个点的点集ps的凸包
poly graham(point* ps, int n)
{
    std::sort(ps, ps + n, cmp);
    poly ans;
    if(n <= 2){
        for(int i = 0; i < n; i++)
        {
            ans.push(ps[i]);
        }
        return ans;
    }
    ans.push(ps[0]);
    ans.push(ps[1]);
    point* tps = ans.ps;
    int top = -1;
    tps[++top] = ps[0];
    tps[++top] = ps[1];
    for(int i = 2; i < n; i++)
    {
        while(top > 0 && xmul(tps[top - 1], tps[top], tps[top - 1], ps[i]) <= 0) top--;
        tps[++top] = ps[i];
    }

    int tmp = top;  //注意要赋值给tmp!

    for(int i = n - 2; i >= 0; i--)
    {
        while(top > tmp && xmul(tps[top - 1], tps[top], tps[top - 1], ps[i]) <= 0) top--;
        tps[++top] = ps[i];
    }
    ans.pn = top;
    return ans;
}
//求点p到st->ed的垂足,列参数方程
point getRoot(point p, point st, point ed)
{
    point ans;
    double u=((ed.x-st.x)*(ed.x-st.x)+(ed.y-st.y)*(ed.y-st.y));
    u = ((ed.x-st.x)*(ed.x-p.x)+(ed.y-st.y)*(ed.y-p.y))/u;
    ans.x = u*st.x+(1-u)*ed.x;
    ans.y = u*st.y+(1-u)*ed.y;
    return ans;
}

//next为直线(st,ed)上的点,返回next沿(st,ed)右手垂直方向延伸l之后的点
point change(point st, point ed, point next, double l)
{
    point dd;
    dd.x = -(ed - st).y;
    dd.y = (ed - st).x;
    double len = sqrt(dd.x * dd.x + dd.y * dd.y);
    dd.x /= len, dd.y /= len;
    dd.x *= l, dd.y *= l;
    dd = dd + next;
    return dd;
}

//求含n个点的点集ps的最小面积矩形,并把结果放在ds(ds为一个长度是4的数组即可,ds中的点是逆时针的)中,并返回这个最小面积。
double getMinAreaRect(point* ps, int n, point* ds)
{
    int cn, i;
    double ans;
    point* con;
    poly tpoly = graham(ps, n);
    con = tpoly.ps;
    cn = tpoly.pn;
    if(cn <= 2)
    {
        ds[0] = con[0]; ds[1] = con[1];
        ds[2] = con[1]; ds[3] = con[0];
        ans=0;
    }
    else
    {
        int  l, r, u;
        double tmp, len;
        con[cn] = con[0];
        ans = 1e40;
        l = i = 0;
        while(dmul(con[i], con[i+1], con[i], con[l])
            >= dmul(con[i], con[i+1], con[i], con[(l-1+cn)%cn]))
        {
            l = (l-1+cn)%cn;
        }
        for(r=u=i = 0; i < cn; i++){
            while(xmul(con[i], con[i+1], con[i], con[u])
                <= xmul(con[i], con[i+1], con[i], con[(u+1)%cn]))
            {
                u = (u+1)%cn;
            }
            while(dmul(con[i], con[i+1], con[i], con[r])
                <= dmul(con[i], con[i+1], con[i], con[(r+1)%cn]))
            {
                r = (r+1)%cn;
            }
            while(dmul(con[i], con[i+1], con[i], con[l])
                >= dmul(con[i], con[i+1], con[i], con[(l+1)%cn]))
            {
                l = (l+1)%cn;
            }
            tmp = dmul(con[i], con[i+1], con[i], con[r]) - dmul(con[i], con[i+1], con[i], con[l]);
            tmp *= xmul(con[i], con[i+1], con[i], con[u]);
            tmp /= dist2(con[i], con[i+1]);
            len = xmul(con[i], con[i+1], con[i], con[u])/dist(con[i], con[i+1]);
            if(sign(tmp - ans) < 0)
            {
                ans = tmp;
                ds[0] = getRoot(con[l], con[i], con[i+1]);
                ds[1] = getRoot(con[r], con[i+1], con[i]);
                ds[2] = change(con[i], con[i+1], ds[1], len);
                ds[3] = change(con[i], con[i+1], ds[0], len);
            }
        }
    }
    return ans+eps;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int Cas = 1; Cas <=t; ++Cas)
    {
        printf("Case #%d:\n",Cas);
        int num = 0;
        scanf("%d",&num);
        for(int i = 0; i < num ; ++i)
        {
            ps[i*4+0].read();
            ps[i*4+1].read();
            ps[i*4+2].read();
            ps[i*4+3].read();
        }
        struct point ds[4];
        double ans = getMinAreaRect(ps,num*4,ds);
        printf("%.0lf\n",ans);
    }
    return 0;
}
View Code

 

目录
相关文章
|
2月前
|
Python
【10月更文挑战第10天】「Mac上学Python 19」小学奥数篇5 - 圆和矩形的面积计算
本篇将通过 Python 和 Cangjie 双语解决简单的几何问题:计算圆的面积和矩形的面积。通过这道题,学生将掌握如何使用公式解决几何问题,并学会用编程实现数学公式。
165 60
|
2月前
|
Python
【10月更文挑战第15天】「Mac上学Python 26」小学奥数篇12 - 图形变换与坐标计算
本篇将通过 Python 和 Cangjie 双语实现图形变换与坐标计算。这个题目帮助学生理解平面几何中的旋转、平移和对称变换,并学会用编程实现坐标变化。
66 1
牛客竞赛21842 正方形检测
牛客竞赛21842 正方形检测
|
7月前
|
数据可视化 开发工具 开发者
羊了个羊游戏开发实战教程(1):堆叠牌的拾取
羊了个羊游戏开发实战教程(1):堆叠牌的拾取
120 0
|
数据可视化 数据挖掘 Python
看世界杯也能学画图:R语言ggplot2画热图展示不同国家历届足球世界杯的成绩
看世界杯也能学画图:R语言ggplot2画热图展示不同国家历届足球世界杯的成绩
|
C++ Python
2022年5月14日LeetCode双周赛第三题-6068. 毯子覆盖的最多白色砖块数
2022年5月14日LeetCode双周赛第三题-6068. 毯子覆盖的最多白色砖块数
2022年5月14日LeetCode双周赛第三题-6068. 毯子覆盖的最多白色砖块数
|
机器学习/深度学习 传感器 算法
2023美赛F题-绿色GDP思路及matlab代码
2023美赛F题-绿色GDP思路及matlab代码
L1-015 跟奥巴马一起画方块 (15 分)
L1-015 跟奥巴马一起画方块 (15 分)
288 0
星空发现图(仿蜗牛梦话圈)
最终效果       直接使用 继承 BaseAdapter 实现onCreateCenter(ViewGroup parent) onCreateChild(ViewGroup parent, T t)方法设置中心View,子View.
1044 1