[HihoCoder]#1360 : 凸多边形

news/2024/4/15 7:54:36

华电北风吹
天津大学认知计算与应用重点实验室
2016-08-14

题目链接:
http://hihocoder.com/problemset/problem/1360

题目分析:
动态规划,思路参考Floyd解决所有节点对的最短路径类型的动态规划。

参考代码:

#include <iostream>
#include <string.h>
#include <algorithm>
#include <iomanip>
using namespace std;#define Length 105struct Point
{int x, y;
};
int N, M;
Point point[Length];
double tringleSize[Length][Length][Length], state[Length][Length][Length];double CalculateTringle(int i, int j, int k)
{return 0.5*(point[i].x * point[j].y + point[j].x * point[k].y + point[k].x * point[i].y - point[i].x * point[k].y - point[j].x * point[i].y - point[k].x * point[j].y);
}int main()
{cin >> N >> M;for (int i = 0; i < N; i++){cin >> point[i].x >> point[i].y;}for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){for (int k = 0; k < N; k++){tringleSize[i][j][k] = abs(CalculateTringle(i, j, k));}}}memset(state, 0, sizeof(state));for (int k = 3; k <= M; k++){for (int i = 0; i < N; i++){for (int j = i + 1; j != i; j = (j + 1) % N){for (int u = i + 1; u != j; u = (u + 1) % N){state[i][j][k] = max(state[i][j][k], state[i][u][k - 1] + tringleSize[u][j][i]);}}}}double result = 0;for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){result = max(result, state[i][j][M]);}}cout << fixed << setprecision(2) << result << endl;return 0;
}

http://www.ppmy.cn/news/215649.html

相关文章

Ubuntu永久更改分辨率1360*768

网上可以搜索到Ubuntu添加新分辨率&#xff08;比如没有1360*768通过xrandr自主创建&#xff09;。但这个方法在reboot之后便会失效&#xff0c;通过半晚上的研究&#xff0c;终于发现了能令Ubuntu添加分辨率格式并保持的方法&#xff08;以1360*768为例&#xff09;。事实上&a…

1360:奇怪的电梯(lift)

【题目描述】 大楼的每一层楼都可以停电梯&#xff0c;而且第i层楼&#xff08;1≤i≤N&#xff09;上有一个数字Ki(0≤Ki≤N&#xff09;。电梯只有四个按钮&#xff1a;开&#xff0c;关&#xff0c;上&#xff0c;下。上下的层数等于当前楼层上的那个数字。当然&#xff0c;…

洛谷CF1360E 多边形

洛谷CF1360E 多边形 题目标签标签难度 思路分析思路一 错因分析AC代码 题目标签 CF1360E 标签 模拟 难度 普及/提高- 思路分析 思路一 时间复杂度 O ( n 2 t ) O(n^2t) O(n2t) 说实在&#xff0c;这一题其实很简单。一道纯模拟题。我们先来分析一下题目&#xff1a;“…

1360. 日期之间隔几天

题目描述 请你编写一个程序来计算两个日期之间隔了多少天。日期以字符串形式给出&#xff0c;格式为 YYYY-MM-DD&#xff0c;如示例所示。示例 1&#xff1a;输入&#xff1a;date1 "2019-06-29", date2 "2019-06-30" 输出&#xff1a;1 示例 2&#xf…

一本通1360 奇怪的电梯

1360&#xff1a;奇怪的电梯(lift) 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 4790 通过数: 2047 【题目描述】 大楼的每一层楼都可以停电梯&#xff0c;而且第i层楼&#xff08;1≤i≤N&#xff09;&#xff08;1≤i≤N&#xff09; 上有一个数字Ki(0≤Ki≤…

LeetCode 1360 - 1363

时间之间隔几天 两个日期之间没有大小关系&#xff0c;可能第 1 个日期大&#xff0c;可能第 2 个日期大&#xff0c;需要同时处理两种情况 1971.1.1 → date1 一共过了 days1 天 1971.1.1 → date2 一共过了 days2 天 | day1 - day2 | 就是答案&#xff0c;因为不知道哪个…

[Codeforces Round #644 (div3)]1360

1360A - Minimal Square[思维] 1360B - Honest Coach[思维] 1360C -Similar Pairs[思维] 1360D - Buying Shovels[思维] 1360E - Polygon[思维] 1360F - Spy-string[暴力] 1360G - A/B Matrix[构造] 1360H - Binary Median[思维] 这场都是思维题&#xff0c;题目就不贴过来了 感…

cf1360G

1360G 1900 题意&#xff1a;对一个长度为m高度为n的全为零二维数组进行操作也就是ar[n][m], 令其每列横行1的个数为a,每排纵行的1的个数为b&#xff0c; 如下所示、 该数组的a2&#xff0c;b1&#xff0c;问你是否存在这么一个ar[n][m]数组使得其满足a和b的要求&#xff0c;…

厦大C语言上机 1360 算日期

1360.算日期 时间限制: 1000 MS 内存限制: 65536 K 提交数: 647 (0 users) 通过数: 286 (279 users) 问题描述 自从收了小明这个徒弟之后&#xff0c;小强的生活就没平静过&#xff0c;小明发扬勤奋好问的精神&#xff0c;总是缠着小强问这问那的。这天&…

ausu-fx80-efi黑苹果10.15.7

因为虚拟机实在太卡了&#xff0c;尝试下了黑苹果&#xff0c;还有一点点的小毛病但是总体我很满意。 这里我分享一下我的笔记本用的EFI。 https://gitee.com/NoCoke/ausu-fx80-g-fx504-ge-efi

华硕fx80笔记本一键u盘安装win8系统图文教程

华硕fx80笔记本是一款2018年上市的家用型游戏影音笔记本电脑&#xff0c;这款电脑搭载了英特尔第八代酷睿i7处理器以及gtx10系列独立显卡&#xff0c;能够满足用户们日常娱乐使用需求&#xff0c;那么华硕fx80笔记本如何一键u盘安装系统呢?今天为大家分享华硕fx80笔记本一键u盘…

飞行堡垒FX80GM热键无反应与触摸板无法使用

快捷键问题&#xff1a; 1.安装hotkey 触摸版问题 2.安装intel serialIO 3.安装touchpad FX80GM - 服务支持

2021-01-06

Vue配置proxy 疯狂的地球人 2021-01-05 12:52:58 13 收藏 分类专栏&#xff1a; Vue学习笔记 文章标签&#xff1a; vue proxy 跨域 ajax跨域问题 devServer 最后发布:2021-01-05 12:52:58 首次发布:2021-01-05 12:52:58 版权声明&#xff1a;本文为博主原创文章&#xff0c…

华硕系列笔记本命名规则以及各型号的差别特点

<script type"text/javascript"> </script><script type"text/javascript" src"http://pagead2.googlesyndication.com/pagead/show_ads.js"> </script> 本人最近想买个本本&#xff0c;收集了些有关信息&#xff0c;希…

重装系统的问题

今天做新系统&#xff0c;因为是500G的空间&#xff0c;想在开始装之前分区&#xff0c;于是用“雨林木风”的自带工具DM进行分区&#xff0c;可是该工具提示“内存不足”。于是&#xff0c;用pq分区&#xff0c;分好后&#xff0c;无论怎么操作&#xff0c;都无法进行ghost。开…

修笔记本电脑(飞行堡垒)

帮别人修一个笔记本&#xff0c;说是运行过程中被拍了一下&#xff0c;然后就读不到其他盘了&#xff0c;只有c盘能用&#xff08;固态加机械&#xff0c;我猜固态是c盘&#xff09;。 把原来的机械硬盘拆下来&#xff0c;换了一个我的机械硬盘&#xff0c;可以开机&#xff0c…

华硕 TUF GAMING FX504GE_FX80GE电脑 Hackintosh 黑苹果efi引导文件

硬件型号驱动情况 主板华硕 FX504GE&#xff08;HM370 芯片组&#xff09; 处理器英特尔 Core i5-8300H 2.30GHz 四核已驱动 内存16GB LPDDR4X 3200MHz已驱动 硬盘金士顿 512G已驱动 显卡Intel UHD630NVIDIA GeForce GTX 1050 Ti ( 屏蔽 )已驱动 声卡瑞昱 英特尔 High Defini…

飞行堡垒fx80g拆卸电源_华硕飞行堡垒第五代FX80拆机加装内存条教程(整盖翻转拆机)...

今天分享一下新买的最新华硕飞型堡垒笔记本FX80的拆机加装内存条的全过程。FX80(几乎今天所有的新一代笔记本都是这样)的后盖是整块的&#xff0c;当新手拿到电脑的时候&#xff0c;可能不敢下手开拆&#xff0c;而此刻博主查阅网上资料&#xff0c;也暂时还没有FX80或者类似型…

华硕fx80装linux,华硕FX80GD笔记本装win7系统及bios设置教程(支持usb)

[文章导读]华硕FX80GD笔记本是一款15.6寸笔记本&#xff0c;2019年发布其搭载intel 酷睿八代处理器。华硕FX80GD笔记本装win7会遇到很多问题&#xff0c;如果用传统方式安装会遇到usb鼠标无法使用问题&#xff0c;且如果是nvme固态安装win7会出现0x0000007b蓝屏&#xff0c;那么…

qt-qss之QCheckbox样式

一、前言 QSlider样式 二、环境 qt5.7 window8 三、正文 效果&#xff1a; qss&#xff1a; QCheckBox{border: none;/*最外层边框*/ } QCheckBox::indicator{/*选择框尺寸*/background-color: rgba(255, 255, 255, 0);border: 0px solid #b1b1b1;width: 30px;height: 30…
最新文章