AOJ 0090 Overlaps of Seals

問題の内容

10*10の正方形上に半径1の円をn個(n<=100)配置する。
最も多くの円の内部に含まれる正方形上の点はいくつの円に含まれるか。
（円の内部とは円周上も含む。）

解法

想定解法では任意の二つの円についてその交点を求め
いくつの円に含まれるかを数えるらしい。

AOJ : 0090 - Overlaps of Seals - Respect2Dの日記
AOJ Problem 0090 : Overlaps of Seals - kyuridenamidaのチラ裏
AOJ 0090: Overlaps of Seals：Snowing day：So-net blog

嘘解法

正方形上の点をできるだけ多く列挙して
その一つ一つについていくつの円に含まれるかを調べる。
円に含まれるかどうかの判定を甘くすると通った。

ソース

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
double x[100],y[100];
int main(){
    int n;
    while(1){
        scanf("%d",&n);
        if(n==0)    break;
        for(int i=0;i<n;i++)
            scanf("%lf,%lf\n",&x[i],&y[i]);
        int ans=0;
        for(double a=0;a<=10.1;a+=0.01)
            for(double b=0;b<=10.1;b+=0.01){
                int t=0;
                for(int i=0;i<n;i++)
                    if((a-x[i])*(a-x[i])+(b-y[i])*(b-y[i])<=1.001)
                        t++;
                ans=max(ans,t);
            }
        printf("%d\n",ans);
    }
    return 0;
}

cabal install monadius したら結構ハマった

結局こんなことをやった

cabal install OpenGLRaw --reinstall
cabal install StateVar --reinstall
cabal install Tensor --reinstall
cabal install ObjectName --reinstall
cabal install OpenGL --reinstall
cabal install GLURaw --reinstall
cabal install array-0.3.0.1 --reinstall
cabal install containers --reinstall
cabal install GLUT --reinstall
cabal install directory-1.1.0.0 --reinstall
cabal install monadius --reinstall

  • history からインストールに必要だと思われるコマンドを抜粋した。
  • よく分からないのでとりあえず全部 --reinstall フラグをつけているけど要らないと思う。

ハマりポイント

cabal install array-0.3.0.1 --reinstall
cabal install directory-1.1.0.0 --reinstall

  • "cabal install array"だけでバージョン指定をしなかったり、"cabal install directory"だけだと最新版を入れようとしてくれるが、入らない。

Haskellで文字列圧縮(エンコーダーのみ）

仕組み

  • 各文字の出現頻度を数えて一番多いものに"1"、二番目に"01"、三番目に"001"を割り振る。
  • ex "aaaaaaaaaaaa" -> "11111111111"
  • その後6ビットずつに区切る
  • ex "11111111111" -> ["111111","111111"]
  • 2進数として読み、文字に変換する
  • ex ["111111","111111"] -> "``"

動作例

Main> compress "aaaaaaaaaaaaabbbbbbbbbbbbbb"
Just "KKKK_`0"
Main> compress "qwerrfvghhvjnbknjkfaghjgfjda"
Just "!1!%!%%%B5B\"#!)A!$)#1;C\"!#1"

課題

文字の種類が多いものはうまく圧縮できない。
生成したビット列の長さが6で割りきれないときは勝手に0を補っている。
返り値が Maybe String 。
デコーダがない。（致命的）

ソースコード

import Data.Map as M
import Data.List
import Data.Char

allChar = Prelude.map chr [0..127]

genDict str = fromList $ Prelude.map func $ zip [1..] $ Prelude.map snd $ reverse $ sort $ zip (Prelude.map (countChar str) allChar) allChar
	where 
		func (a,b) = (b,makeCodeLengthN a)
		makeCodeLengthN 1 = "1"
		makeCodeLengthN n = '0' : makeCodeLengthN (n-1)
		countChar [] _ = 0
		countChar (x:xs) c = if x==c
			then 1 + countChar xs c
			else countChar xs c

translate [] d = return []
translate (x:xs) d = do
	y <- M.lookup x d
	ys <- translate xs d
	return (y++ys)

bitToChar str = func (reverse str) 0
	where
		func [] a = chr (33+a)
		func (x:xs) a = if x=='1'
			then func xs (a*2+1)
			else func xs (a*2)

split6 str = if length str < 6
	then [str]
	else fst (splitAt 6 str) : split6 (snd (splitAt 6 str) )

compress str = do
	a <- translate str $ genDict str
	return ( Prelude.map bitToChar (split6 a) )

std::setでデータ同士の間に順位付けができないと無視されてしまう件 

#include <stdio.h>
#include <set>
using namespace std;
struct Data{
	int a,b;
};
Data makeD(int aa,int bb){
	Data d;
	d.a=aa,d.b=bb;
	return d;
}
bool operator < (const Data &d,const Data &e){
	return d.a<e.a;
}
int main(){
	set<Data> se;
	se.insert(makeD(0,1));
	se.insert(makeD(0,2));
	printf("se.size()==%d\n",se.size());
	for(set<Data>::iterator it=se.begin();it!=se.end();it++)
		printf("a=%d b=%d\n",(*it).a,(*it).b);
	return 0;
}

を実行すると

se.size()==1
a=0 b=1

となってしまう。
これはsetが(0,1)と(0,2)の違いを分からないからである。

se.size()==2
a=0 b=1
a=0 b=2

このようにするには

bool operator < (const Data &d,const Data &e){
        if(d.a==e.a)           //<=
               return d.b<e.b; //<=
	return d.a<e.a;
}

こんな風に書き換えると良い。