`

hdu3684

 
阅读更多

/*
刚开始打了个记录上下左右四个点的,一直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;
}
 
分享到:
评论

相关推荐

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    hdu2101解决方案

    hdu2101AC代码

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu.

    【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...

    Hdu1000—2169部分代码

    HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    HDU acm-PPT课件

    【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...

    hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084

    【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...

    HDU最全ac代码

    HDU(Hangzhou Dianzi University)是国内外知名的在线编程竞赛平台,主要服务于ACM/ICPC(国际大学生程序设计竞赛)以及相关的算法训练。"HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码...

    hdu动态规划算法集锦

    根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...

Global site tag (gtag.js) - Google Analytics