oldsnuke/input.cpp

## input.cpp
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<algorithm>
#include <ctime>
using namespace std;


bool map[500][500];


int main(){
	int n, x, y;

	srand( (unsigned)time( NULL ) );

	freopen("in.txt","w",stdout);

	scanf("%d",&n);//頂点数
	printf("%d\n", n);

	for(int i = 0; i < n; i++){
		while(1){
			x = rand()%500;
			y = rand()%500;

			if(!map[x][y]){
				map[x][y] = true;
				printf("%d %d\n",x,y);
				break;
			}
		}
	}

	return 0;
}

## read me
imosさんにもらったビジュアライザーで表示させています。
ビジュアライザーとdata.jsは同じディレクトリにして下さい。

voronoi.cppにはバグが残っていて、
1. x座標かy座標の同じ２点があると高確率でバグる（それぞれ違うところでバグが発生する。）
2. たまに謎なバグが発生する（特に頂点数が増えたとき）

1については入力データを自動生成するプログラムの方をいじって解決したw


気が向いたらデバッグしてうpするかも

## view.html
<script>
function line(x,y,a,b){c.b();c.moveTo(x,y);c.lineTo(a,b);c.s();}
function circle(x,y,r){c.b();c.arc(x,y,r,0,7,0);c.s();}
function circlec(x,y,r,a){fillcolor(a);c.b();c.arc(x,y,r,0,7,0);c.fill();}
function fillcolor(x){if(x!=undefined)c.fillStyle=x;}
function poly(x,a){fillcolor(a);c.b();c.moveTo(x[x.length-1][0],x[x.length-1][1]);for(var i=0;i<x.length;i++)c.lineTo(x[i][0],x[i][1]);c.closePath();c.fill();}
window.onload=function(){d=document;d.i=d.getElementById;
c=d.i('c').getContext('2d');c.b=c.beginPath;c.s=c.stroke;
d.i('s').src='data.js?';};
</script>
<body><canvas id="c" width="500" height="500" style="border:1px solid #000;"></canvas>
<script id="s"></script></body>

## voronoi.cpp
#include<cstdio>
#include<vector>
#include<list>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define fi first
#define se second
using namespace std;

typedef pair<double, double> P;


const int INF = 100000000;
const double wx = 500, wy = 500;

int px[1000], py[1000];
double la[1000][1000], lb[1000][1000];


list<P> cell;


int main(){
	srand( (unsigned)time( NULL ) );

	int n, m, u, wp, vp;
	double x, y, nx, ny, mx, my;
	P w, v, ca, cb;
	list<P>::iterator k, h, ed;

	freopen("in.txt","r",stdin);
	freopen("data.js","w",stdout);

	scanf("%d",&n);
	for(int i = 0; i < n; i++){
		scanf("%d%d",&px[i], &py[i]);
	}

	for(int i = 0; i < n; i++){

		cell.push_back(P(0.0,0.0));
		cell.push_back(P(0.0,wy));
		cell.push_back(P(wx,wy));
		cell.push_back(P(wx,0.0));

		for(int j = 0; j < n; j++){
			if(i == j) continue;
			x = px[j] - px[i]; y = py[j] - py[i];
			if(y == 0){
				la[i][j] = INF;
				lb[i][j] = (px[j] + px[i]) / 2;
			} else {
				la[i][j] = -x/y;
				lb[i][j] = (py[i] + py[j] + x/y*(px[i] + px[j])) / 2;

				wp = INF; vp = INF; u = 0; m = 0;
				if(la[i][j] * (py[i]-lb[i][j] - la[i][j]*px[i]) < 0) u = 1;

				for(k = cell.begin(); k != cell.end(); k++){
					ca = *k;
					h = k;
					h++;
					if(h == cell.end()){
						cb = *(cell.begin());
					} else {
						cb = *h;
					}
					if ((ca.se-lb[i][j] - la[i][j]*ca.fi) * (cb.se-lb[i][j] - la[i][j]*cb.fi) < 0){

						x = ca.fi - cb.fi; y = ca.se - cb.se;
						if(x == 0){
							if(wp == INF){
								w = P(ca.fi, la[i][j]*ca.fi + lb[i][j]);
								wp = m;
							} else {
								v = P(ca.fi, la[i][j]*ca.fi + lb[i][j]);
								vp = m;
							}

						} else {
							nx = y/x;
							ny = ca.se - ca.fi*nx;
							mx = (lb[i][j] - ny)/(nx - la[i][j]);
							my = la[i][j] * mx + lb[i][j];

							if(wp == INF){
								w = P(mx,my);
								wp = m;
							} else {
								v = P(mx,my);
								vp = m;
							}
						}
					}

					m++;
				}


				if(wp != INF){
					if(w.se > v.se){ swap(w, v); swap(wp, vp);}

					m = 0;
					if(wp > vp) m = 1;

					k = cell.begin();
					for(int l = 0; l < wp; l++) k++;
					h = cell.begin();
					for(int l = 0; l < vp; l++) h++;
					if(k == cell.end()){
						k = cell.insert(cell.begin(), w);
					} else {
						k++;
						k = cell.insert(k, w);
					}
					if(h == cell.end()){
						h = cell.insert(cell.begin(), v);
					} else {
						h++;
						h = cell.insert(h, v);
					}

					if(m) swap(k,h);

					if((u+m)%2){
						k++;
						cell.erase(k, h);
					} else {
						ed = cell.end(); ed--;
						if(h != ed){
							h++;
							cell.erase(h, cell.end());
						}
						if(k != cell.begin()){
							cell.erase(cell.begin(), k);
						}
					}
				}
			}

		}

		ed = cell.end(); ed--;
		ca = *ed;
		for(k = cell.begin(); k != cell.end(); k++){
			printf("line(%lf,%lf,%lf,%lf)\n",(*k).fi,(*k).se, ca.fi,ca.se);
			ca = *k;
		}
		printf("poly([");
		for(k = cell.begin(); k != cell.end(); k++){
			if(k != cell.begin()) printf(",");
			printf("[%lf,%lf]",(*k).fi,(*k).se);
		}
		int aho = rand()%175+80;
		//aho = 255;
		printf("],'#%02x%02x%02x')\n",aho,aho,aho);

		cell.clear();
	}

	for(int i = 0; i < n; i++){
		printf("circle(%d, %d, 0.5)\n", px[i], py[i]);
	}

	return 0;
}
	#include<cstdlib>
	#include<cstdio>
	#include<vector>
	#include<algorithm>
	#include <ctime>
	using namespace std;


	bool map[500][500];


	int main(){
	int n, x, y;

	srand( (unsigned)time( NULL ) );

	freopen("in.txt","w",stdout);

	scanf("%d",&n);//頂点数
	printf("%d\n", n);

	for(int i = 0; i < n; i++){
	while(1){
	x = rand()%500;
	y = rand()%500;

	if(!map[x][y]){
	map[x][y] = true;
	printf("%d %d\n",x,y);
	break;
	}
	}
	}

	return 0;
	}
	imosさんにもらったビジュアライザーで表示させています。
	ビジュアライザーとdata.jsは同じディレクトリにして下さい。

	voronoi.cppにはバグが残っていて、
	1. x座標かy座標の同じ２点があると高確率でバグる（それぞれ違うところでバグが発生する。）
	2. たまに謎なバグが発生する（特に頂点数が増えたとき）

	1については入力データを自動生成するプログラムの方をいじって解決したw


	気が向いたらデバッグしてうpするかも
	<script>
	function line(x,y,a,b){c.b();c.moveTo(x,y);c.lineTo(a,b);c.s();}
	function circle(x,y,r){c.b();c.arc(x,y,r,0,7,0);c.s();}
	function circlec(x,y,r,a){fillcolor(a);c.b();c.arc(x,y,r,0,7,0);c.fill();}
	function fillcolor(x){if(x!=undefined)c.fillStyle=x;}
	function poly(x,a){fillcolor(a);c.b();c.moveTo(x[x.length-1][0],x[x.length-1][1]);for(var i=0;i<x.length;i++)c.lineTo(x[i][0],x[i][1]);c.closePath();c.fill();}
	window.onload=function(){d=document;d.i=d.getElementById;
	c=d.i('c').getContext('2d');c.b=c.beginPath;c.s=c.stroke;
	d.i('s').src='data.js?';};
	</script>
	<body><canvas id="c" width="500" height="500" style="border:1px solid #000;"></canvas>
	<script id="s"></script></body>
	#include<cstdio>
	#include<vector>
	#include<list>
	#include<algorithm>
	#include<cstdlib>
	#include<ctime>
	#define fi first
	#define se second
	using namespace std;

	typedef pair<double, double> P;


	const int INF = 100000000;
	const double wx = 500, wy = 500;

	int px[1000], py[1000];
	double la[1000][1000], lb[1000][1000];


	list<P> cell;




	int main(){
	srand( (unsigned)time( NULL ) );

	int n, m, u, wp, vp;
	double x, y, nx, ny, mx, my;
	P w, v, ca, cb;
	list<P>::iterator k, h, ed;

	freopen("in.txt","r",stdin);
	freopen("data.js","w",stdout);

	scanf("%d",&n);
	for(int i = 0; i < n; i++){
	scanf("%d%d",&px[i], &py[i]);
	}

	for(int i = 0; i < n; i++){

	cell.push_back(P(0.0,0.0));
	cell.push_back(P(0.0,wy));
	cell.push_back(P(wx,wy));
	cell.push_back(P(wx,0.0));

	for(int j = 0; j < n; j++){
	if(i == j) continue;
	x = px[j] - px[i]; y = py[j] - py[i];
	if(y == 0){
	la[i][j] = INF;
	lb[i][j] = (px[j] + px[i]) / 2;
	} else {
	la[i][j] = -x/y;
	lb[i][j] = (py[i] + py[j] + x/y*(px[i] + px[j])) / 2;

	wp = INF; vp = INF; u = 0; m = 0;
	if(la[i][j] * (py[i]-lb[i][j] - la[i][j]*px[i]) < 0) u = 1;

	for(k = cell.begin(); k != cell.end(); k++){
	ca = *k;
	h = k;
	h++;
	if(h == cell.end()){
	cb = *(cell.begin());
	} else {
	cb = *h;
	}
	if ((ca.se-lb[i][j] - la[i][j]ca.fi) (cb.se-lb[i][j] - la[i][j]*cb.fi) < 0){

	x = ca.fi - cb.fi; y = ca.se - cb.se;
	if(x == 0){
	if(wp == INF){
	w = P(ca.fi, la[i][j]*ca.fi + lb[i][j]);
	wp = m;
	} else {
	v = P(ca.fi, la[i][j]*ca.fi + lb[i][j]);
	vp = m;
	}

	} else {
	nx = y/x;
	ny = ca.se - ca.fi*nx;
	mx = (lb[i][j] - ny)/(nx - la[i][j]);
	my = la[i][j] * mx + lb[i][j];

	if(wp == INF){
	w = P(mx,my);
	wp = m;
	} else {
	v = P(mx,my);
	vp = m;
	}
	}
	}

	m++;
	}


	if(wp != INF){
	if(w.se > v.se){ swap(w, v); swap(wp, vp);}

	m = 0;
	if(wp > vp) m = 1;

	k = cell.begin();
	for(int l = 0; l < wp; l++) k++;
	h = cell.begin();
	for(int l = 0; l < vp; l++) h++;
	if(k == cell.end()){
	k = cell.insert(cell.begin(), w);
	} else {
	k++;
	k = cell.insert(k, w);
	}
	if(h == cell.end()){
	h = cell.insert(cell.begin(), v);
	} else {
	h++;
	h = cell.insert(h, v);
	}

	if(m) swap(k,h);

	if((u+m)%2){
	k++;
	cell.erase(k, h);
	} else {
	ed = cell.end(); ed--;
	if(h != ed){
	h++;
	cell.erase(h, cell.end());
	}
	if(k != cell.begin()){
	cell.erase(cell.begin(), k);
	}
	}
	}
	}

	}

	ed = cell.end(); ed--;
	ca = *ed;
	for(k = cell.begin(); k != cell.end(); k++){
	printf("line(%lf,%lf,%lf,%lf)\n",(k).fi,(k).se, ca.fi,ca.se);
	ca = *k;
	}
	printf("poly([");
	for(k = cell.begin(); k != cell.end(); k++){
	if(k != cell.begin()) printf(",");
	printf("[%lf,%lf]",(k).fi,(k).se);
	}
	int aho = rand()%175+80;
	//aho = 255;
	printf("],'#%02x%02x%02x')\n",aho,aho,aho);

	cell.clear();
	}

	for(int i = 0; i < n; i++){
	printf("circle(%d, %d, 0.5)\n", px[i], py[i]);
	}

	return 0;
	}