2008 Belt

まわすたいぷの平面走査であることはわかりましたが、どうやってその平面走査処理するのがいいかな〜と。
各頂点を中心にしたものに対し適当に二回やったやつだとなんか処理いみふになったので、冷静に考えた結果1回ぐるぐる回せば何とかなるだろうと書いたら通りました。

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int x[1000];
int y[1000];
pair<double,int> L[8000];
int X[1000];
int Y[1000];
int main(){
	int a;
	double PI=3.14159265359;
	double b;
	scanf("%d%lf",&a,&b);
	for(int i=0;i<a;i++)scanf("%d%d",x+i,y+i);
	int ret=0;
	for(int i=0;i<a;i++){
		int now=0;
		for(int j=0;j<a;j++){
			X[j]=x[j]-x[i];
			Y[j]=y[j]-y[i];
		}
		int val=0;
		for(int j=0;j<a;j++){
			if(b*2/sqrt(X[j]*X[j]+Y[j]*Y[j])<1.0){
				L[now++]=make_pair(atan2(Y[j],X[j]),1);
				L[now++]=make_pair(atan2(Y[j],X[j])+asin(b*2/sqrt(X[j]*X[j]+Y[j]*Y[j])),2);
				L[now++]=make_pair(atan2(Y[j],X[j])+PI-asin(b*2/sqrt(X[j]*X[j]+Y[j]*Y[j])),1);
				L[now++]=make_pair(atan2(Y[j],X[j])+PI,2);
				L[now++]=make_pair(atan2(Y[j],X[j])+PI*2,1);
				L[now++]=make_pair(atan2(Y[j],X[j])+PI*2+asin(b*2/sqrt(X[j]*X[j]+Y[j]*Y[j])),2);
				L[now++]=make_pair(atan2(Y[j],X[j])+PI*3-asin(b*2/sqrt(X[j]*X[j]+Y[j]*Y[j])),1);
				L[now++]=make_pair(atan2(Y[j],X[j])+PI*3,2);
			}else{
				L[now++]=make_pair(atan2(Y[j],X[j]),1);
				L[now++]=make_pair(atan2(Y[j],X[j])+PI,2);
				L[now++]=make_pair(atan2(Y[j],X[j])+PI*2,1);
				L[now++]=make_pair(atan2(Y[j],X[j])+PI*3,2);
			}
		}
		std::sort(L,L+now);
		ret=max(ret,val);
		for(int j=0;j<now;j++){
			if(L[j].second==1){
				val++;
			}else val--;
			ret=max(ret,val);
		}
	//	printf("\n");
	}
	printf("%d\n",ret);
}

2008もやっと10完。残りが本当にヤバゲ。

残った問題たち(OutputOnlyとSALTをのぞく)

• 2007-DAY3-3 (Circuit) 3 sec 64 MB

出力がUniqueじゃないのでJudgeが動かない。なのであんまりやる気しない。けどどうせ数学？
2008-DAY4-1 (Ruins) 1.5 sec 64 MB
未だに通ってないが、この中では簡単なほうだと思う。DP。
2009-DAY3-1 (Territory) 1 sec 64 MB
よくわかっていない。この年のDay3難しすぎだと思う。

• 2009-DAY3-3 (Logo) 3 sec 64 MB

これも出力がUniqueじゃないのでJudgeは動いてないのでやってないのだが、相当やばい問題に見える。
2011-DAY1-2 (Dragon) 10 sec 64 MB
なぜか通ってくれないのでまた書く。
2011-DAY2-3 (Shiritori) 5 sec 64 MB
やたらと難化した2011の中での最難問。合宿で一番グラフ度高い問題だと思う。余裕があったら後で考えよう。