[HDU 4855] Goddess (极角排序+三分)

2024-06-21 20:08

本文主要是介绍[HDU 4855] Goddess (极角排序+三分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

HDU - 4855
借这道题学了下极角排序和三分求凸函数最大值
按所有左右切线,圆心的弧度值排序,从而分割出角度上的若干个区间
射线的角度在这些区间里变动时,每个割线的长度都是凸函数,叠加起来也是凸函数
所以可以对每个区间利用三分法求得最大值,再对这些最大值取 max 即为答案

1) 利用三分法可以求得单峰函数的最大值
2) 利用 atan2(y,x)可以比较方便地求出向量与 x轴正方向的夹角,取值范围 [-Pi,Pi],从逆时针旋转 Pi 到顺时针旋转 Pi
但是排序后要插入两个额外的角, -Pi和 Pi,这是为了防止有圆穿过 x负半轴,而无法进行比较
3) 计算圆是否与射线相交时,可以利用旋转矩阵旋转射线和圆心,将射线与 x正半轴对齐
此时距离即为旋转后圆心的 y坐标,x坐标若为负数,则表明圆在射线另一侧

#if _WIN32||_WIN64
#define lld I64d
#define llu I64u
#endif
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> Pii;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define LL long long
#define ULL unsigned long long
int maxx(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
int abss(int a){return a<0?(-a):a;}const double eps=1e-11,PI=acos(-1.0);
struct Circle
{double x,y,r;
};
struct Vector
{double x,y;Vector(double tx=0, double ty=0):x(tx),y(ty){};
};double VLen(Vector u){return sqrt(u.x*u.x+u.y*u.y);}
double operator ^ (Vector u, Vector v){return u.x*v.y-u.y*v.x;}int N,ap;
Circle inpt[250];
double angl[800];double calc(double);int main()
{while(~scanf("%d", &N)){ap=0;angl[++ap]=PI;angl[++ap]=-PI; // to calculate the circle go across the x-asisfor(int i=1; i<=N; i++){scanf("%lf%lf%lf", &inpt[i].x, &inpt[i].y, &inpt[i].r);double acent=atan2(inpt[i].y,inpt[i].x);double distc=VLen(Vector(inpt[i].x,inpt[i].y));double delta=asin(inpt[i].r/distc);double ang1=acent-delta,ang2=acent+delta;if(ang1<-PI&&fabs(ang1+PI)>eps) ang1+=2*PI;if(ang2>PI&&fabs(ang2-PI)>eps) ang2-=2*PI;angl[++ap]=acent;angl[++ap]=ang1;angl[++ap]=ang2;}sort(angl+1,angl+1+ap);ap=unique(angl+1,angl+1+ap)-angl-1;double ans=0.0;
//      for(int i=1; i<=ap; i++) printf("%lf\n", angl[i]);for(int i=1; i<ap; i++){double l=angl[i],r=angl[i+1];double res=0;while(l<r&&fabs(l-r)>eps){
//              printf("l:%f r:%f res:%f\n", l, r, res);system("pause");double ll=l+(r-l)/3;double rr=l+2*(r-l)/3;double resl=calc(ll);double resr=calc(rr);if(resl>resr){res=resl;r=rr-eps;}else{res=resr;l=ll+eps;}if(res>ans&&fabs(res-ans)>eps) ans=res;}}printf("%.8f\n", ans);}return 0;
}double calc(double ang)
{double m11=cos(ang),m12=sin(ang),m21=-sin(ang),m22=cos(ang);// use matrix to rotate the center of circlesdouble temp=0.0;for(int i=1; i<=N; i++){double x=m11*inpt[i].x+m12*inpt[i].y; // has the same direction with the laserdouble y=fabs(m21*inpt[i].x+m22*inpt[i].y); // the distance to the laserif((y<inpt[i].r&&fabs(y-inpt[i].r)>eps)&&(x>0)){temp+=2*sqrt(inpt[i].r*inpt[i].r-y*y);}}return temp;
}

这篇关于[HDU 4855] Goddess (极角排序+三分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin