World Final Training 3 —— ICPC Asia Jakarta Regional Site 2012(3 unsolved)

edward_mj 21 12 月, 201222 12 月, 2012 有 4 条评论

一个冬至啊……就在训练和听逻辑实验复习大会中过去了555 >_<
觉得训练没有记录不太科学，一来方便自己以后看吧，二来方便找训练中没有过的题。
这场之所以选Jakarta是因为今天CF挂了……
Board

从Board里面可以看到我们一个小时45分钟就6题了，然后我去收了个快递。回来prowindy过掉了G。
然后后面3个小时就没过过题……
比赛过程就不说了，反正就是没什么策略地做了。
Problem D

先判点在多边形内，得到点集，然后问一个给定的点，在这个点集里的最近点和次近点的id。

很显然这个old的模板题，先是判点在多边形内，然后可以用KDTree做。具体做法是取最近点，然后remove掉，再取，最后把删的点insert回去。但是不知道为什么WA到死。
后来我发现很可能的一个原因是我用int读入的，但是题目其实没说有没有可能是实数，anyway，等fix了再确定吧。

Problem F
什么绳子打结然后问可不可能的……完全不知道怎么搞。

Problem H

快速选中离给定点曼哈顿距离<=d的点，然后对他们模拟一下。如此重复。

这题我没有碰，其实坐标旋转以后KDTree也轻松搞的，但是zYc和prowindy都不太熟这方面的内容，也写了一段时间但没调出来。

Summary
F是真的被智商碾压了。其它的D、H都是二维数据结构模板(old?)的题。在这种题上失利不是一次两次的事情了，包括今年杭州的区域赛。所以我觉得有必要对这个专题专门去搞搞。KDTree我自己写的不是很熟练，所以要么是再写写熟，要么就备一个模板好了。

Unsolved list:
D
F
H

加入对话

4条评论

求I的做法

#include
#include
#include
#include
using namespace std;
typedef pair pii;
struct vec{
	int x,y;
	vec(){}
	vec(int a,int b):x(a),y(b){}
	vec& read(){scanf("%d %d",&x,&y);return *(this);}
	const vec operator +(const vec& r)const{
		return vec(x+r.x,y+r.y);
	}
	const vec operator -(const vec& r)const{
		return vec(x-r.x,y-r.y);
	}
	int operator *(const vec& r)const{
		return x*r.y-y*r.x;
	}
	const vec operator*(int r)const{
		return vec(r*x,r*y);
	}
	const vec gcd(const vec & r)const{
		return vec(__gcd(x,r.x),__gcd(y,r.y));
	}
	bool zero(){return x==0 && y==0;}
};
int gao(const vec &a,const vec& b,const vec &c){
	int t=a*b;
	if(t){
		int p =c*b/t,
			q =a*c/t,
			w = 1999999999;
		vec nc,tmp;
		for(int dp=-1;dp<=1;++dp)
			for(int dq=-1;dq<=1;++dq){
				tmp = c-a*(p+dp)-b*(q+dq);
				if(abs(tmp*a)

zYc说是水过去的……

zYc说：

22 12 月, 2012 10:56 下午

当只有两个向量时，答案就是它们的外积的绝对值。
如果3个向量中的两个是中有一个是另外一个的scalar multiple,这两个就可以被它们的最大公约向量所替代。
a,b,c是三个向量,p,q是整数,(a,b,c-pa-qb)与(a,b,c)所能表示的点是一样的。(a,b,c)->(c-pa-qb,a,b)这样不断迭代到有两个向量平行为止。为了使迭代可以终止，用a、b线性表示c，由于是p、q整数在比较接近的9组参数(p,q)中选与a外积最小的那个,这样似乎可以保证迭代在有限步内终止…..

回复

zYc说：

22 12 月, 2012 10:55 下午

当只有两个向量时，答案就是它们的外积的绝对值。
如果3个向量中的两个是中有一个是另外一个的scalar multiple,这两个就可以被它们的最大公约向量所替代。
a,b,c是三个向量,p,q是整数,(a,b,c-pa-qb)与(a,b,c)所能表示的点是一样的。(a,b,c)->(c-pa-qb,a,b)这样不断迭代到有两个向量平行为止。为了使迭代可以终止，用a、b线性表示c，由于是p、q整数在比较接近的9组参数(p,q)中选与a外积最小的那个,这样似乎可以保证迭代在有限步内终止。

回复

World Final Training 3 —— ICPC Asia Jakarta Regional Site 2012(3 unsolved)

加入对话

留下评论

取消回复