コード:
#pragma warning(disable:4996) // 警告を消します
#pragma warning(disable:4146) // 警告を消します
#include "DxLib.h"
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <sstream>
using namespace std ;
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 各種構造体
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 線分と矩形を表す構造体
struct LINE {
int pos1X,pos1Y,pos2X,pos2Y;
LINE(): pos1X(0),pos1Y(0),pos2X(0),pos2Y(0) {}
LINE(int sx,int sy,int dx,int dy): pos1X(sx),pos1Y(sy),pos2X(dx),pos2Y(dy) {}
};
struct SQUARE {
int pos1X,pos1Y,pos2X,pos2Y;
SQUARE(): pos1X(0),pos1Y(0),pos2X(0),pos2Y(0) {}
SQUARE(int sx,int sy,int dx,int dy): pos1X(sx),pos1Y(sy),pos2X(dx),pos2Y(dy) {}
};
// 座標を表す構造体
struct POSITION {
int x,y;
POSITION(): x(0),y(0) {}
POSITION(int ix,int iy): x(ix),y(iy) {}
};
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 各種クラス
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 擬似的な二次元配列を動的に確保するためのクラス
template<class T>
class virtual_2d_array {
T* buffer;
size_t x_size,y_size;
public:
virtual_2d_array() {
buffer=new T[1];
x_size=y_size=1;
}
~virtual_2d_array() {delete[] buffer;}
// 要素数を[y][x]に指定する
void resize(size_t y,size_t x) {
delete[] buffer;
buffer=new T[x*y];
x_size=x;
y_size=y;
}
virtual_2d_array(size_t y,size_t x) {
buffer=new T[1];
resize(y,x);
}
T* operator[](size_t idx) {return buffer+x_size*idx;}
const T* operator[](size_t idx) const {return buffer+x_size*idx;}
// 配列の要素全体を指定した値で埋める
void fill_all(const T& value) {
fill(buffer,buffer+x_size*y_size,value);
}
};
// 二次元BITのクラス
class bit_2d {
virtual_2d_array<int> bit2d_table;
size_t bit_max_x,bit_max_y;
void internal_add(int* array, size_t pos, int value) {
pos++;
while(pos<=bit_max_x) {
array[pos-1]+=value;
pos+=pos & (-pos);
}
}
int internal_sum(const int* array, size_t pos) const {
int sum=0;
pos++;
while(pos>0) {
sum+=array[pos-1];
pos-=pos & (-pos);
}
return sum;
}
public:
// 初期化する
void clear() {
bit2d_table.fill_all(0);
}
// 要素数を設定する
void resize(size_t y_size,size_t x_size) {
bit2d_table.resize(y_size,x_size);
bit_max_x=x_size;
bit_max_y=y_size;
}
bit_2d(): bit_max_x(0),bit_max_y(0) {}
bit_2d(size_t y_size,size_t x_size) {
resize(y_size,x_size);
}
// (x,y)にvalueを加える
void add(size_t x,size_t y,int value) {
y++;
while(y<=bit_max_y) {
internal_add(bit2d_table[y-1],x,value);
y+=y & (-y);
}
}
// [0,x]×[0,y]の和を求める
int sum(size_t x,size_t y) const {
int sum=0;
y++;
while(y>0) {
sum+=internal_sum(bit2d_table[y-1],x);
y-=y & (-y);
}
return sum;
}
// [sx,dx)×[sy,dy)にvalueを塗る(いもす法相当)
void add2(int sx,int sy,int dx,int dy,int value) {
if(sx<0)sx=0;
if(sy<0)sy=0;
if(sx>=(int)bit_max_x || sy>=(int)bit_max_y)return;
add(sx,sy,value);
if(dx<(int)bit_max_x)add(dx,sy,-value);
if(dy<(int)bit_max_y)add(sx,dy,-value);
if(dx<(int)bit_max_x && dy<(int)bit_max_y)add(dx,dy,value);
}
// [sx,dx)×[sy,dy)の和を求める
int sum2(int sx,int sy,int dx,int dy) const {
int ret=0;
dx--;dy--;
if(dx<0 || dy<0)return 0;
if(dx>=(int)bit_max_x)dx=bit_max_x-1;
if(dy>=(int)bit_max_y)dy=bit_max_y-1;
ret=sum(dx,dy);
if(sx>0)ret-=sum(sx-1,dy);
if(sy>0)ret-=sum(dx,sy-1);
if(sx>0 && sy>0)ret+=sum(sx-1,sy-1);
return ret;
}
};
// 座標圧縮を行うクラス
class coord_compresser {
int* coords;
size_t coords_num;
size_t buffer_num;
public:
// 座標を指定し、圧縮する
void set_coords(const int* coord_array,size_t n) {
if(n>buffer_num) {
if(coords!=NULL)delete[] coords;
coords=new int[n];
buffer_num=n;
}
copy(coord_array,coord_array+n,coords);
sort(coords,coords+n);
coords_num=(int)(unique(coords,coords+n)-coords);
}
coord_compresser(): coords(NULL),coords_num(0),buffer_num(0) {}
coord_compresser(const int* coord_array,size_t n) {
coords=NULL;
coords_num=0;
buffer_num=-1;
set_coords(coord_array,n);
}
~coord_compresser() {delete[] coords;}
// 指定されたインデックスの座標を取得する
int operator[](size_t idx) const {return coords[idx];}
// 圧縮後の座標の数を取得する
size_t size() const {return coords_num;}
// 確保されたバッファのサイズを取得する
size_t capacity() const {return buffer_num;}
// 指定した座標の圧縮後のインデックスを取得する
int indexOf(int coord) const {
return (int)(lower_bound(coords,coords+coords_num,coord)-coords);
}
};
// 線分で囲まれている場所を覆う矩形を見つける処理本体を行うクラス
class square_finder {
// 何回も計算する時にいちいち再確保しなくていいように、メモリを使いまわすためメンバ変数で持つ
virtual_2d_array<int> grid;
coord_compresser coord_x,coord_y;
bit_2d bit;
int *coord_x_buf,*coord_y_buf;
size_t buffer_size;
public:
square_finder(): coord_x_buf(NULL),coord_y_buf(NULL),buffer_size(0) {}
~square_finder() {
if(coord_x_buf!=NULL)delete[] coord_x_buf;
if(coord_y_buf!=NULL)delete[] coord_y_buf;
}
// メモリの確保を行う
void reserve(size_t size) {
if(size>buffer_size) {
if(coord_x_buf!=NULL)delete[] coord_x_buf;
if(coord_y_buf!=NULL)delete[] coord_y_buf;
buffer_size=size;
coord_x_buf=new int[buffer_size*2];
coord_y_buf=new int[buffer_size*2];
grid.resize(buffer_size*4+1,buffer_size*4+1);
bit.resize(buffer_size*2,buffer_size*2);
}
}
vector<SQUARE*> get_squares(const vector<LINE*>& line);
};
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 各種関数
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 線分で囲まれている部分を適当な矩形に分割する
// 線分の数をNとして、O(N^2 log N)だと思う
std::vector<SQUARE*> square_finder::get_squares(const std::vector<LINE*>& line) {
// 線分が無いなら、自明に矩形は存在しない
if(line.empty())return std::vector<SQUARE*>();
// 必要ならバッファの再確保を行う
reserve(line.size());
size_t n=line.size();
// 座標圧縮の準備
for(size_t i=0;i<n;i++) {
if(line[i]->pos1X!=line[i]->pos2X && line[i]->pos1Y!=line[i]->pos2Y) {
// 入力が無効(線分がナナメ)
return std::vector<SQUARE*>();
}
coord_x_buf[i*2]=line[i]->pos1X;
coord_x_buf[i*2+1]=line[i]->pos2X;
coord_y_buf[i*2]=line[i]->pos1Y;
coord_y_buf[i*2+1]=line[i]->pos2Y;
}
// 座標圧縮
coord_x.set_coords(coord_x_buf,n*2);
coord_y.set_coords(coord_y_buf,n*2);
size_t x_size=coord_x.size();
size_t y_size=coord_y.size();
size_t grid_x_size=x_size*2+1;
size_t grid_y_size=y_size*2+1;
// いもす法でグリッド上に線分を描く
grid.fill_all(0);
// 線分を置く
for(size_t i=0;i<n;i++) {
LINE& l=*line[i];
int sx=coord_x.indexOf(min(l.pos1X,l.pos2X))*2+1;
int sy=coord_y.indexOf(min(l.pos1Y,l.pos2Y))*2+1;
int dx=coord_x.indexOf(max(l.pos1X,l.pos2X))*2+1;
int dy=coord_y.indexOf(max(l.pos1Y,l.pos2Y))*2+1;
grid[sy][sx]++;
grid[sy][dx+1]--;
grid[dy+1][sx]--;
grid[dy+1][dx+1]++;
}
// 累積和を取る
for(size_t y=0;y<grid_y_size;y++) {
for(size_t x=1;x<grid_x_size;x++)grid[y][x]+=grid[y][x-1];
}
for(size_t x=0;x<grid_x_size;x++) {
for(size_t y=1;y<grid_y_size;y++)grid[y][x]+=grid[y-1][x];
}
// 幅優先探索で矩形ではない場所に印をつける
std::queue<POSITION> search_queue;
search_queue.push(POSITION(0,0));
grid[0][0]=1;
while(!search_queue.empty()) {
static const int dx[4]={1,0,-1,0};
static const int dy[4]={0,1,0,-1};
POSITION now_coord=search_queue.front();
search_queue.pop();
for(int i=0;i<4;i++) {
int nx=now_coord.x+dx[i];
int ny=now_coord.y+dy[i];
if(0<=nx && nx<(int)grid_x_size && 0<=ny && ny<(int)grid_y_size && grid[ny][nx]==0) {
grid[ny][nx]=1;
search_queue.push(POSITION(nx,ny));
}
}
}
// 印が付いていない場所について、二次元BITに値を足していく
bit.clear();
for(size_t y=0;y<y_size;y++) {
for(size_t x=0;x<x_size;x++) {
if(grid[y*2+2][x*2+2]==0)bit.add(x,y,1);
}
}
// 二次元BITを用いて矩形を検出し、リストに挿入した後消す
// 左上から右に順にスキャンし、貪欲に矩形を埋めていく
std::vector<SQUARE*> squares;
for(size_t y=0;y<y_size;y++) {
for(size_t x=0;x<x_size;x++) {
if(bit.sum2(x,y,x+1,y+1)==1) {
size_t left,right;
// x方向の二分探索
left=x;right=x_size-1;
while(left<=right) {
size_t mid=(left+right)/2;
if(bit.sum2(x,y,mid+1,y+1)==(int)(mid-x+1)) {
left=mid+1;
} else {
right=mid-1;
}
}
size_t dx=left-1;
// y方向の二分探索
left=y;right=y_size-1;
while(left<=right) {
size_t mid=(left+right)/2;
if(bit.sum2(x,y,dx+1,mid+1)==(int)((dx-x+1)*(mid-y+1))) {
left=mid+1;
} else {
right=mid-1;
}
}
size_t dy=left-1;
// 矩形を登録する
squares.push_back(new SQUARE(coord_x[x],coord_y[y],coord_x[dx+1],coord_y[dy+1]));
// BITから今登録した矩形に該当する部分を消す
for(size_t y2=y;y2<=dy;y2++) {
for(size_t x2=x;x2<=dx;x2++)bit.add(x2,y2,-1);
}
}
}
}
return squares;
}
// int型を文字列に変換する関数
string IntToString( const int & number )
{
stringstream ss ;
ss << number ;
return ss.str() ;
}
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// WinMain
//+++++++++++++++++++++++++++++++++++++++++++++++++++
int WINAPI WinMain( HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow )
{
// ウィンドウモードにする
ChangeWindowMode( TRUE ) ;
// DXライブラリ初期化処理
if( DxLib_Init() == -1 ){ return -1 ; }
// 線分を複数保持する配列
vector<LINE *> lines(0) ; // とりあえずサイズ0としておきます
// 矩形を複数保持する配列
std::vector<SQUARE*> squares(0) ; // とりあえずサイズ0としておきます
// 矩形を見つける処理本体クラス
square_finder sf ;
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 線分を思いつくまま追加します
// ※以下は、実験用に固定で追加しますが、
// 本来は、長さ、本数、追加順が不定です
// 斜めの線は無い、ということだけ決まっています
//+++++++++++++++++++++++++++++++++++++++++++++++++++
//// 線分を追加
lines.push_back( new LINE( 100, 100, 300, 100 ) ) ;
lines.push_back( new LINE( 300, 300, 300, 100 ) ) ;
lines.push_back( new LINE( 100, 300, 300, 300 ) ) ;
lines.push_back( new LINE( 100, 300, 100, 100 ) ) ;
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 矩形を算出する処理
//+++++++++++++++++++++++++++++++++++++++++++++++++++
int startTime = GetNowCount() ;
squares = sf.get_squares( lines );
int endTime = GetNowCount() ;
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 画面表示する処理
//+++++++++++++++++++++++++++++++++++++++++++++++++++
// 矩形を表示する
for( int i=0, n=squares.size() ; i<n ; ++i )
{
DrawBox( squares[i]->pos1X, squares[i]->pos1Y, squares[i]->pos2X, squares[i]->pos2Y, GetColor( 255, 0, 0 ), TRUE ) ;
}
// 線分を表示する
for( int i=0, n=lines.size() ; i<n ; ++i )
{
DrawLine( lines[i]->pos1X, lines[i]->pos1Y, lines[i]->pos2X, lines[i]->pos2Y, GetColor( 255, 255, 255 ) ) ;
}
// 処理時間を描画する
string mes = "処理時間=" + IntToString( ( endTime - startTime ) / 1000 ) + "秒" ;
DrawString( 0, 0, mes.c_str(), GetColor( 255, 255, 255 ) ) ;
// メモリを解放する
for( vector<LINE*>::iterator it=lines.begin();it!=lines.end();it++)
{
delete[] *it;
}
for( vector<SQUARE*>::iterator it=squares.begin();it!=squares.end();it++)
{
delete[] *it;
}
// キー入力待ち
WaitKey() ;
// DXライブラリ使用の終了処理
DxLib_End() ;
// ソフトの終了
return 0 ;
}