题目链接:uva 1543 - Telescope
题目大意:按照逆时针的顺序给出单位圆上的点(按照百分比),然后给出k,要求选出k个点组成的多边形面积最大,输出最大值。
解题思路:一开始想错方向了,状态都想好了,但是不知怎么求面积,一直想着说一圆心和圆上两点去求面积,但是这样就有说圆形在多边形外部的可能。后来想到海伦公式,根据三条边的长度求面积,然后圆是个环状的。所以将dp数组放大一倍。dp[i][j][k]表示从第i个点到第j个点选k个点的最大面积(i,j必须选)
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 50;
const double pi = atan(1.0) * 4;
int n, k;
double dp[N][N][N];
double p[N], d[N][N], area[N][N][N];
inline double dis(int x, int y) {
double a = p[y] - p[x];
if (a > 0.5)
a = 1 - a;
return 2 * sin(a*pi);
}
inline double getArea(double x, double y, double z) {
double tmp = (x + y + z)/2;
return sqrt(tmp * (tmp - x) * (tmp - y) * (tmp - z));
}
void init () {
for (int i = 0; i < n; i++)
scanf("%lf", &p[i]);
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
d[i][j] = d[j][i] = dis(i, j);
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
for (int t = j+1; t < n; t++) {
double tmp = getArea(d[i][j], d[j][t], d[t][i]);
area[i][j][t] = area[i][t][j] = tmp;
area[j][i][t] = area[j][t][i] = tmp;
area[t][i][j] = area[t][j][i] = tmp;
}
}
}
}
double solve () {
memset(dp, 0, sizeof(dp));
for (int i = 3; i <= k; i++) {
for (int x = 0; x < n; x++) {
for (int y = x+1; y < n; y++) {
for (int z = y+1; z < n; z++)
dp[x][z][i] = max(dp[x][z][i], dp[x][y][i-1] + area[x][y][z]);
}
}
}
double ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
ans = max(ans, dp[i][j][k]);
}
}
return ans;
}
int main () {
while (scanf("%d%d", &n, &k) == 2 && n + k) {
init ();
printf("%.6lf\n", solve());
}
return 0;
}
分享到:
相关推荐
Arduino-Telescope-Control, 带 Stellarium python 和Arduino的望远镜控制 带Stellarium和Arduino的望远镜控制方案由scratch单片机 gnu microcontroller和软件组成,采用scratch单片机实现了对望远镜机构的控制,并...
import telescope from 'vue-telescope' import "./assets/styling/index.css"; const app = createApp(App) app.use(telescope) app.mount('#app') < p xss=removed>truncated text 输出 设定值 {length: Number...
:green_heart:安装npm install -g vue-telescope-analyzer # Or yarn global add vue-telescope-analyzer用法vta [url]# Examplevta https://fr.nuxtjs.org 它支持多种, 和。构架 要支持新的Vue框架,请查看 。UI...
任何建议或改进将受到... 在这里查看:backhand_index_pointing_right_light_skin_tone:egeres.github.io/star-telescope 码头工人 docker build -t star-telescope . && docker run -p 5000:5000 --rm star-telescope
首先安装Telescope并检查其是否有效(请参阅 ) composer require laravel/telescope php artisan telescope:install php artisan migrate 然后只需使用Composer安装该软件包,它将自动注册: composer require ...
Plug ' nvim-telescope/telescope-fzf-native.nvim ' , { ' do ' : ' make ' } 打包程序 use { ' nvim-telescope/telescope-fzf-native.nvim ' , run = ' make ' } 望远镜的设置和配置: require ( ' telescope ' )...
如果当前用户无法根据 gate viewTelescope定义的访问策略访问Telescope Debug Assistant ,则链接会自动禁用。 有关更多信息,请查看。 演示 安装 首先,通过composer安装: composer require mad-web/nova-...
telescope-symbols为其用户提供了选择符号并将其插入到点的能力。 安装 Plug ' nvim-telescope/telescope-symbols.nvim ' 用法 运行:Telescope symbols将使用所有内置源填充符号选择器。 否则,如果要使用单个或多...
Adaptive beam shaping for improving the power coupling of a two-Cassegrain-telescope
telescope-project.nvim 的扩展,允许您切换项目。 演示版 设置 您可以通过在配置中添加以下内容来设置扩展程序: require ' telescope ' . load_extension ( ' project ' ) 可用功能: 项目 项目选择器。 ...
Telescope-media-files.nvim 使用Telescope预览Neovim的图像,pdf,epub,视频和字体。 仅在LINUX上受支持 安装 Plug ' nvim-lua/popup.nvim ' Plug ' nvim-lua/plenary.nvim ' Plug ' nvim-telescope/telescope....
muon_telescope 由E. Ricci( )撰写,用于特伦托大学的核和亚核物理课程的实验技术。 基于GEANT4的B2b示例。 编译代码: $ mkdir build $ cd build $ cmake $ make 要运行代码: $ ./exampleB2b 有用的命令:...
Telescope是一个由构建的开源实时社交新闻网站注意: Telescope是Beta版软件。 它的大多数应该可以工作,但仍然略有修饰,您可能会发现一些错误。 使用后果自负:) 请注意,Telescope是根据我们需要您的帮助! ...
克隆它并复制到您的 openshift 文件夹以将流星望远镜应用程序推送到 openshift。
一个示例 Telescope 项目。 安装 ,在本地克隆此存储库,然后使用以下命令运行应用程序: meteor您可以选择通过自定义包自定义您的应用程序。 要启用提供的自定义包模板,只需键入: meteor add my-custom-package...
arduino望远镜跟踪赤道仪的基本RA跟踪和运动控制成分: Arduino纳米DRV8825步进电机驱动器HC-05蓝牙模块12V至5V降压转换器
望远镜频率扩展,在从编辑历史记录中选择文件时提供智能优先级。 使用Mozilla的的实现(在使用),frecently编辑的文件列表中的索引被赋予更高的优先级。 随着扩展程序逐渐了解您的编辑习惯,列表的排序会动态更改,...
望远镜作弊尝试使用lua,neovim, 和telescope.nvim重新创建cheat.sh。安装Plug ' tami5/sql.nvim 'Plug ' nvim-telescope/telescope-cheat.nvim 'lua require ' telescope ' . load_extension ( " cheat " )用法:...
与github cli Telescope-github.nvim集成与github cli集成安装您需要先安装github cli安装Github cli插件'nvim-lua / popup.nvim'插件'nvim-lua / plenary.nvim'插件'nvim-telescope / telescope.nvim'插件'nvim-...
vimspector与telescope.nvim的集成Telescope-vimspector.nvim vimspector与telescope.nvim的集成演示安装插件'puremourning / vimspector'插件'nvim-lua / popup.nvim'插件'nvim-lua / plenary.nvim'插件'nvim -...