首页 > 编程语言 >第十届中国大学生程序设计竞赛 哈尔滨站(CCPC 2024 Harbin Site)

第十届中国大学生程序设计竞赛 哈尔滨站(CCPC 2024 Harbin Site)

时间:2024-11-06 19:19:58浏览次数:2  
标签:std 多边形 int hull Site CCPC 2024 leq points

B. Concave Hull

题目描述

简单多边形是平面中由线段组成的闭合曲线,这些线段首尾相连,除了因连接共用的线段端点,任何两
个线段都不能彼此相交。

简单多边形可以分为两类:凸多边形和凹多边形。一个凸多边形是指:多边形中任意两点间的线段上的
所有点都在多边形内,包括在内部或边界上。不是凸多边形的简单多边形就是凹多边形。如图,左边
是一个凸多边形,右边是一个凹多边形。

现在,给定 n 个点,满足所有点互不相同,且不存在三个点在同一条直线上。你的任务是选择这 n 个点
中的一些点(可以全选),并按照任意顺序依次连边,最后需要连成一个面积严格大于 0 的凹多边形。
你需要求出能形成的凹多边形的面积最大是多少。

输入描述

第一行一个正整数 \(T\) \((1 \leq T \leq 10^4)\),表示数据组数。

对于每组数据,第一行一个正整数 \(n\) \((3 \leq n \leq 10^5)\),表示点数。

接下来 \(n\) 行,每行两个整数 \(x_i\), \(y_i\) \((−10^9 \leq x_i, y_i \leq 10^9)\),表示各个点的坐标。保证所有点的坐标互不相
同,且不存在三点共线。

各个测试数据组的 \(n\) 之和不超过 \(2 · 10^5\)。

输出描述

对于每组数据,如果不能形成面积严格大于 \(0\) 的凹多边形,输出 \(−1\);否则,输出一个正整数,表示形成的最大的凹多边形的面积的两倍。可以证明这个答案是一个正整数。

解题思路

对于凸多边形来说,显然凸包就是答案,而凹多边形的最大面积显然就是将凸包上的某一点由凸变凹(去掉那个小三角形),也就是枚举凸包上的边并找到离这个边最近的点,直接暴力枚举会超时,但是不难发现这些点都有个特征:它们都位于去除构成凸包的点后,剩余点构成的凸包上,因此双指针扫描一遍即可。

代码实现

#include <bits/stdc++.h>

#define int long long

struct Point {
    int x, y;

    bool operator<(const Point &p) const {
        return x < p.x || (x == p.x && y < p.y);
    }

    bool operator==(const Point &p) const {
        return x == p.x && y == p.y;
    }

};

// 向量叉积求三点面积的两倍
int cross(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

// andrew构建凸包
std::vector<Point> andrew(std::vector<Point> points) {
    std::sort(points.begin(), points.end());
    std::vector<Point> hull;

    // 需要特判一下剩余点集不能构成封闭图形的情况
    if (points.size() <= 2) {
        return points;
    }

    for (int i = 0; i < 2; i++) {
        int st = hull.size();
        for (const auto p: points) {
            while (hull.size() >= st + 2 && cross(hull[hull.size() - 2], hull.back(), p) <= 0) {
                hull.pop_back();
            }
            hull.push_back(p);
        }
        hull.pop_back();
        std::reverse(points.begin(), points.end());
    }

    if (hull.size() > 1 && hull.front() == hull.back()) {
        hull.pop_back();
    }
    return hull;
}

// 求凸包面积
int area(const std::vector<Point> &points) {
    int res = 0;
    int n = points.size();
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        res += points[i].x * points[j].y - points[j].x * points[i].y;
    }
    return std::abs(res);
}


signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int t;
    std::cin >> t;

    while (t--) {
        int n;
        std::cin >> n;

        std::vector<Point> points1(n), points2;
        for (int i = 0; i < n; i++) {
            std::cin >> points1[i].x >> points1[i].y;
        }

        // 构建外层凸包
        std::vector<Point> hull1 = andrew(points1), hull2;
        std::set<Point> st;
        for (auto p: hull1) {
            st.insert(p);
        }

        for (auto p: points1) {
            if (!st.count(p)) {
                points2.push_back(p);
            }
        }

        // 构建内层凸包
        hull2 = andrew(points2);

        // 特判点集只能构成凸包
        if (hull2.size() == 0) {
            std::cout << -1 << "\n";
            continue;
        }


        int pos = 0, min1 = 4e18, siz1 = hull1.size(), siz2 = hull2.size();
        Point p1 = hull1[0], p2 = hull1[1];
        for (int i = 0; i < siz2; i++) {
            Point p3 = hull2[i];
            if (cross(p1, p2, p3) < min1) {  // 初始化需要去掉的最小面积并记录位置
                min1 = cross(p1, p2, p3);
                pos = i;
            }
        }

        // 末尾防越界直接开两倍
        for (int i = 0; i < siz2; i++) {
            hull2.push_back(hull2[i]);
        }
        siz2 = hull2.size();

        int lastpos = pos;  // 上一次最小的位置
        for (int i = 1; i < siz1; i++) {
            p1 = hull1[i], p2 = hull1[i + 1];  // 枚举外层凸包上的点
            lastpos = pos;
            int min2 = 4e18;
            while (lastpos < siz2) {  // 枚举内层凸包上的点
                Point p3 = hull2[lastpos];
                if (min2 > cross(p1, p2, p3)) {
                    min2 = cross(p1, p2, p3);
                    min1 = std::min(min1, min2);  // 更新最小值和位置
                    pos = lastpos;
                    lastpos++;
                } else {
                    break;
                }
            }
        }

        std::cout << area(hull1) - min1 << "\n";
    }
}

标签:std,多边形,int,hull,Site,CCPC,2024,leq,points
From: https://www.cnblogs.com/udiandianis/p/18530817

相关文章

  • TPAMI 2024 | NICEST:用于鲁棒场景图生成的噪声标签修正与训练
    题目:NICEST:NoisyLabelCorrectionandTrainingforRobustSceneGraphGenerationNICEST:用于鲁棒场景图生成的噪声标签修正与训练作者:LinLi;JunXiao;HanrongShi;HanwangZhang;YiYang;WeiLiu;LongChen摘要几乎所有现有的场景图生成(SGG)模型都忽视......
  • HNCPC2024
    E拼接串题目描述给出一个长度为\(n\)的正整数串\(a\)。现在可以把两个没有重叠的连续子串前后拼接起来,但是要求拼接之后的数串中每个正整数不能出现超过\(1\)次。请问能拼接出来的符合要求的数字串的最大长度是多少。输入描述第一行一个整数\(n\)\((1\leqn\leq1,......
  • 2024网络安全面试题大全(附答案详解)看完表示入职大厂稳了
    今天为大家各大厂面试题1.深信服面试题难度系数:中一面:时间太久了,记不太清了,难度相对还是可以的二面:~sql注入的原理是什么–本质:将用户输入的不可信数据当作代码去执行–条件:用户能控制输入;;;原本程序要执行的代码,拼接了用户输入的内容,然后执行~说说Linux的信号机制?~J......
  • 20222323 2024-2025-1 《网络与系统攻防技术》实验四实验报告
    一、实验内容(一)恶意代码文件类型标识、脱壳与字符串提取对提供的rada恶意代码样本,进行文件类型识别,脱壳与字符串提取,以获得rada恶意代码的编写作者,具体操作如下:(1)使用文件格式和类型识别工具,给出rada恶意代码样本的文件格式、运行平台和加壳工具;(2)使用超级巡警脱壳机等脱壳软件,......
  • CCPC Final 2023 B. Periodic Sequence
    https://vjudge.net/problem/QOJ-8543给定\(n\),对于\(i=1,2,\ldots,n\)求出最长可能的周期字符串序列长度F(i),满足序列中字符串的长度\(≤i\)。一个字符串序列\(S_1,S_2,\ldots,S_l\)是周期字符串序列,当且仅当对于每个\(1≤i<l\)都满足\(S_i\)是\(S_{i+1}\)的周期......
  • zlibrary中文版入口及电子书客户端/app(2024更新)
    Z-library是一个全球范围内庞大的数字图书馆之一,其藏书量非常丰富。截至最新数据,Z-library共收录了超过9,826,996册电子书以及84,837,646篇学术期刊文章。这个数字图书馆覆盖了从经典文学巨著到前沿理工学科,从人文艺术瑰宝到专业学术论文的广泛领域,几乎能够满足每一位求知者的阅读......
  • 百万年薪!2024 Salesforce高薪职位排行
    随着Salesforce在全球的普及,这一平台不仅带来了新的职场机会,更为从业者提供了优渥的薪资待遇。最近的Salesforce薪资调查显示,Salesforce生态系统中不同职位的薪资水平相当可观,尤其在美国市场,一些顶级岗位的年薪可达到令人惊叹的百万级别。今天我们就来细数2024年Salesforce的十......
  • 浏览器是如何渲染页面的? - 2024最新版前端秋招面试短期突击面试题
    浏览器是如何渲染页面的?-2024最新版前端秋招面试短期突击面试题【100道】......
  • NOIP2024加赛2
    NOIP2024加赛2题目来源:2023NOIPA层联测18\(T1\)HZTG5733.新的阶乘\(100pts\)预处理素数后直接对\(1\simn\)进行质因数分解因为有太多冗余枚举导致无法通过。考虑枚举最终形式。具体地,从质因数的角度入手,设当前枚举的质数为\(p\),暴力求出\(ip\)中\(p\)的指......
  • P11227 [CSP-J 2024] 扑克牌(官方数据)
    P11227[CSP-J2024]扑克牌(官方数据)1#include<bits/stdc++.h>2usingnamespacestd;3intn;4chars[5];5intpoker[5][15];67intget1(){//返回花色12348if(s[0]=='D')return1;9elseif(s[0]=='C')return2;10......