G - Glyph Recognition Gym - 101623G(计算几何+二分)

2024-04-15 23:48

本文主要是介绍G - Glyph Recognition Gym - 101623G(计算几何+二分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:
在这里插入图片描述

弄两个多边形覆盖图中所有点,要求里面多边形面积比上外面多边形面积值最大。

思路:
枚举用的是哪个多边形,则比值最大时,外面那个多边形覆盖所有点,里面那个多边形一个点都没有覆盖。二分就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>using namespace std;const double eps = 1e-8;
const double pi = acos(-1);const int maxn = 1e3 + 7;
struct point
{double x,y;int id;point(){}point(double _x,double _y){x = _x;y = _y;}point operator+(point a){return point(x + a.x,y + a.y);}point operator-(point a){return point(x - a.x,y - a.y);}double operator*(point a){return x * a.y - y * a.x;}}a[maxn],p[10][15];
int n;
bool dcmp(double x,double y)
{if(x - y < eps && x - y > -eps)return 0;if(x - y > 0)return 1;return -1;
}double cal(point *p) { //算凸包面积double ans = 0;int cnt = p[0].id + 3;for(int i = 0;i < cnt - 1;i++){ans += (p[i] - p[0]) * (p[i + 1] - p[0]);}return fabs(ans) / 2;
}bool judge(point now,point *p,double mid) { //now是否在多边形内now.x /= mid;now.y /= mid;int cnt = p[0].id + 3;double ans = 0.0;for(int i = 0;i < cnt;i++) {point p1 = p[i % cnt],p2 = p[(i + 1) % cnt];ans += fabs((p1 - now) * (p2 - now));}ans = ans / 2;double area = cal(p);if(dcmp(area,ans) == 0) return true;return false;
}bool check1(double mid,point *p) { //覆盖所有点for(int i = 0;i < n;i++) {if(!judge(a[i],p,mid)) return false;}return true;
}bool check2(double mid,point *p) { //是否没有覆盖点for(int i = 0;i < n;i++) {if(judge(a[i],p,mid)) return false;}return true;
}void init() {for(int i = 0;i <= 5;i++) {for(int j = 0;j < i + 3;j++) {p[i][j].id = i;double rad = 2 * pi / (i + 3) * j;double x = cos(rad),y = sin(rad);p[i][j].x = x;p[i][j].y = y;}    }
}int main() {#ifndef ONLINE_JUDGEfreopen("D:in.in", "r", stdin);freopen("D:out.out", "w", stdout);#endifinit();scanf("%d",&n);for(int i = 0;i < n;i++) {scanf("%lf%lf",&a[i].x,&a[i].y);}double ans = 0.0;int pos = 0;for(int i = 0;i <= 5;i++) {double l = 0,r = 5e7;double ans1 = 0.0;double ans2 = 0.0;while(r - l > eps) { //外层比例double mid = (l + r) / 2;if(check1(mid,p[i])) {r = mid;} else {l = mid;}}ans1 = l * l;l = 0,r = 5e7;while(r - l > eps) {double mid = (l + r) / 2;if(check2(mid,p[i])) {l = mid;} else {r = mid;}}ans2 = r * r;if(ans < ans2 / ans1) {ans = ans2 / ans1;pos = i;}}printf("%d %.8f\n",pos + 3,ans);return 0;
}

这篇关于G - Glyph Recognition Gym - 101623G(计算几何+二分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/907264

相关文章

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

如何用Java结合经纬度位置计算目标点的日出日落时间详解

《如何用Java结合经纬度位置计算目标点的日出日落时间详解》这篇文章主详细讲解了如何基于目标点的经纬度计算日出日落时间,提供了在线API和Java库两种计算方法,并通过实际案例展示了其应用,需要的朋友... 目录前言一、应用示例1、天安门升旗时间2、湖南省日出日落信息二、Java日出日落计算1、在线API2

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

uva 10387 Billiard(简单几何)

题意是一个球从矩形的中点出发,告诉你小球与矩形两条边的碰撞次数与小球回到原点的时间,求小球出发时的角度和小球的速度。 简单的几何问题,小球每与竖边碰撞一次,向右扩展一个相同的矩形;每与横边碰撞一次,向上扩展一个相同的矩形。 可以发现,扩展矩形的路径和在当前矩形中的每一段路径相同,当小球回到出发点时,一条直线的路径刚好经过最后一个扩展矩形的中心点。 最后扩展的路径和横边竖边恰好组成一个直

poj 1113 凸包+简单几何计算

题意: 给N个平面上的点,现在要在离点外L米处建城墙,使得城墙把所有点都包含进去且城墙的长度最短。 解析: 韬哥出的某次训练赛上A出的第一道计算几何,算是大水题吧。 用convexhull算法把凸包求出来,然后加加减减就A了。 计算见下图: 好久没玩画图了啊好开心。 代码: #include <iostream>#include <cstdio>#inclu

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

XTU 1237 计算几何

题面: Magic Triangle Problem Description: Huangriq is a respectful acmer in ACM team of XTU because he brought the best place in regional contest in history of XTU. Huangriq works in a big compa