- 浏览: 388612 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (229)
- java编程 (4)
- java实用程序 (2)
- 算法设计 (34)
- 数据库 (8)
- ACM模板 (12)
- 技术术语 (1)
- java_web (3)
- php (22)
- eclipse (3)
- linux (25)
- linux命令使用心得 (3)
- web服务器 (8)
- IT知识 (2)
- 前端技术 (17)
- 开源软件 (5)
- vim (3)
- linux多线程 (9)
- web开发经验 (3)
- lua (5)
- linux编程 (3)
- smarty (1)
- mysql (4)
- Hive (2)
- 数据挖掘 (9)
- python (2)
- 生活 (1)
- C++ (2)
- 计算机 (1)
- objective-c (11)
- css (2)
- 游戏 (1)
- Mac (1)
最新评论
-
lr544463316:
我的怎么不行呀.....
Mysql Access denied for user ''@'localhost' to database 的一种解决方法 -
babaoqi:
使用时需要注意group_concat函数返回值的最大长度=g ...
mysql中的group_concat函数 -
代码能力弱成渣:
可以帮我看下我的代码么?我自己写的sam,也有ac过题的,但是 ...
求两个字符串的最长公共连续子序列(SAM实现) -
atgoingguoat:
有1000个?不过还是收藏下。
jquery常用的插件1000收集(转载)
/* 刚开始打了个记录上下左右四个点的,一直tle。 研究了isun大牛的代码后发现原来可以更简单………… */ #include <cstdio> #include <algorithm> #include <cmath> using namespace std; typedef double typev; const int N=105; const int Q=1005; const int M=10005; const double eps=1e-8; const double pi=acos(-1.0); int sign(double d){ return d<-eps?-1:(d>eps); } struct point{ typev x, y; point(double _x=0, double _y=0):x(_x), y(_y){} point operator-(point tp){ return point(x-tp.x, y-tp.y); } double operator^(point tp){ return x*tp.y-y*tp.x; } void read(){ scanf("%lf%lf", &x, &y); } }hull[N][Q], ps[Q]; struct ray{ point st, v; double ang; int id; bool operator<(const ray& _ray)const{ return ang<_ray.ang; } }; int hn[N], n, m; int ls[N], rs[N]; int ans[M]; ray rays[M]; bool cmp(point d1, point d2){ return d1.x < d2.x || (d1.x == d2.x && d1.y < d2.y); } typev xmul(point st1, point ed1, point st2, point ed2){ return (ed1.x-st1.x) * (ed2.y-st2.y) - (ed1.y-st1.y) * (ed2.x-st2.x); } //对ps求凸包,结果放在hull里 void graham(point* ps, int n, point* hull, int& hn){ int i; if(n<=2){ hn=n; for(i=0; i<n; i++){ hull[i]=ps[i]; } return; } sort(ps, ps+n, cmp); hull[0] = ps[0]; hull[1] = ps[1]; int top = 1; for(i = 2; i < n; i++){ while(top > 0 && xmul(ps[i], hull[top-1], ps[i], hull[top]) >= 0) top--; hull[++top] = ps[i]; } int tmp = top; for(i = n-2; i >= 0; i--){ while(top > tmp && xmul(ps[i], hull[top-1], ps[i], hull[top]) >= 0) top--; hull[++top] = ps[i]; } hn = top; hull[hn] = hull[0]; } bool input(){ scanf("%d", &n); int i, j, qn; for(i=0; i<n; i++){ scanf("%d", &qn); for(j=0; j<qn; j++){ ps[j].read(); } graham(ps, qn, hull[i], hn[i]); //保证点是逆时针方向的 reverse(hull[i], hull[i]+hn[i]); } scanf("%d", &m); for(i=0; i<m; i++){ rays[i].st.read(); rays[i].v.read(); rays[i].id=i; rays[i].ang=atan2(rays[i].v.y, rays[i].v.x); } return true; } void solve(){ sort(rays, rays+m); int i, j, u; point *h; point a, b, c, d; ray r; for(i=0; i<n; i++){ ls[i]=rs[i]=0; } for(i=0; i<m; i++){ u=-1; r=rays[i]; for(j=0; j<n; j++){ h=hull[j]; while((r.v^h[(ls[j]+1)%hn[j]]-h[ls[j]]) > 0){ ls[j]=(ls[j]+1)%hn[j]; } while((r.v^h[(ls[j]-1+hn[j])%hn[j]]-h[ls[j]]) > 0){ ls[j]=(ls[j]-1+hn[j])%hn[j]; } while((r.v^h[(rs[j]+1)%hn[j]]-h[rs[j]])<0){ rs[j]=(rs[j]+1)%hn[j]; } while((r.v^h[(rs[j]-1+hn[j])%hn[j]]-h[rs[j]])<0){ rs[j]=(rs[j]-1+hn[j])%hn[j]; } if((h[rs[j]]-h[ls[j]]^r.st-h[ls[j]])>0) continue; if(sign(r.v^h[ls[j]]-r.st)*sign(r.v^h[rs[j]]-r.st)>0) continue; if(u==-1){ u=j; }else{ a=h[ls[j]]; b=h[rs[j]]; c=hull[u][ls[u]]; d=hull[u][rs[u]]; if(((b-a^c-a)>0 && (b-a^c-a)>0) || ((d-c^a-c)<0 && (d-c^b-c)<0)){ u=j; } } } ans[r.id]=u; } for(i=0; i<m; i++){ if(ans[i]==-1){ printf("MISS\n"); }else{ printf("HIT %d\n", ans[i]); } } printf("*****\n"); } int main(){ // freopen("in.txt", "r", stdin); int t; scanf("%d", &t); while(t--){ input(); solve(); } return 0; }
发表评论
-
升序数组中求一个key出现的次数
2013-01-09 23:08 1109算法思路: 在排好序的数组,相同的数字是排列在一起的,所以只需 ... -
判断单链表是否有环
2013-01-08 19:07 921算法思路: 指针p1和p2的起始值均为链表的表头,指针p1每次 ... -
hdu3686
2011-11-14 20:43 1035/* 无向图边的双连通分量,在同一个连通分量里的边之间 ... -
poj3968
2011-11-14 04:45 1415source: http://poj.org/problem ... -
uva2819
2011-11-13 02:20 900source: http://livearchive.onli ... -
manacher算法
2011-11-11 00:06 2434const int LEN=110005; const ... -
hdu4118
2011-11-09 21:53 1192枚举每条边最多被经过的次数即可 #include ... -
hdu4115
2011-11-09 16:27 1040source: http://acm.hdu.edu.cn/ ... -
uva(Transitive Closure)
2011-11-08 14:45 918source: http://livearchive.onli ... -
zoj3500
2011-11-07 17:41 956求两个球的体积交或者并 #include <cs ... -
zoj3545
2011-11-04 18:18 868/* AC自动机 相当暴力的 解法: mark[i ... -
zoj3190
2011-11-04 17:34 1317/* * AC自动机,先对资源串和病毒串构成的字符串 ... -
zoj3228
2011-11-04 16:12 949/* * AC自动机,每个节点 添加一个d表示节点代 ... -
poj3691(DNA Repair)
2011-11-04 13:18 1481/* AC自动机,增设虚拟节点,求长度为n的字符串中包 ... -
hdu2825
2011-11-04 11:53 993/* AC自动机,增设虚拟节点,求长度为n的字符 ... -
hdu4095
2011-11-03 13:19 1020/* 第一步,构建BST,用第一个数作为bst的 ... -
zoj3540
2011-11-02 21:33 927/* 其实就是把总共的 放置次数减去不能放置的那些就行 ... -
poj1741(树的分治,基于边的 分治)
2011-11-02 20:25 3358/* 树基于边的分治算法,计算树中距离小于等于k的点 ... -
hdu2939
2011-10-29 18:36 859source: http://acm.hdu.edu.cn/s ... -
hdu3982
2011-10-29 10:20 948//半平面交+多边形和圆的交的面积 #include ...
相关推荐
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
hdu2101AC代码
【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...
【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...
HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...
【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...
HDU(Hangzhou Dianzi University)是国内外知名的在线编程竞赛平台,主要服务于ACM/ICPC(国际大学生程序设计竞赛)以及相关的算法训练。"HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码...
根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...