'넓이'에 해당되는 글 2건

  1. 2016.04.13 가장 넓은 직사각형 구하는 알고리즘 ( O(MN) )
  2. 2011.09.12 [Math] 사선 공식
Coding/CPP 삽질기2016. 4. 13. 18:00

가장 넓은 직사각형 구하는 알고리즘 ( O(MN) )

가장 넓은 직사각형 구하는 알고리즘 ( O(MN) )


/*
From :
http://stackoverflow.com/questions/7245/puzzle-find-largest-rectangle-maximal-rectangle-problem
*/

int findMaxRect (int rect[XSIZE][YSIZE]) {
	int ret = 0;
	unsigned int x = 0, y = 0, k = 0;
	int sum[YSIZE+1] = { 0, };
	int stack[YSIZE][2] = { 0, };
	int stIdx = -1;
	int width = 0;
	int y0 = 0, w0 = 0, tempArea = 0;
	
	for ( x = 0; x < XSIZE; ++x ) { 
		for ( y = 0; y <= YSIZE; ++y ) {
			sum[y] = rect[y][x] ? ++sum[y] : 0;
		}
		sum[YSIZE] = 0;
		width = 0;
		stIdx = -1;
		for ( y = 0; y <= YSIZE; ++y) {
			if ( sum[y] > width ) {
				stack[++stIdx][0] = y;
				stack[  stIdx][1] = width;
				width = sum[y];				
			} 
			else if ( sum[y] < width ) {

				while(1) {
					y0 = stack[stIdx  ][0];
					w0 = stack[stIdx--][1];
					tempArea =  width * (y - y0);
				  
					ret = tempArea > ret ? tempArea : ret;

					width = w0;
					if( sum[y] >= width) break;
				} 
				width = sum[y];
				if ( width != 0 ) {
					stack[++stIdx][0] = y0;
					stack[  stIdx][1] = w0;	
				}
			}
		}
	}	
	
	return ret;
}


저작자표시

'Coding > CPP 삽질기' 카테고리의 다른 글

Bit 연산 정리  (0) 2016.08.20
printf로 디버깅 하기  (0) 2016.04.13
C++ 컴파일러  (0) 2016.03.30
Posted by chobocho
Coding/Math2011. 9. 12. 00:51

[Math] 사선 공식

임의의 점들을 이은 다각형의(볼록 다각형) 넓이를 구하는 공식인 사선공식 이다.



삼각형의 넓이를 구 할 때에도 헤론의 공식 보다 C로 구현하기가 간단하다.


//
// Java 로 구현한 사선 공식
//

    import java.lang.Math;

    public double getArea(Point[] arrPoints) {
        double area = 0.0;
        
        Point tempPoint = new Point(arrPoints[0]);
        
        for ( int i = 1; i < arrPoints.length; i++) {
            area += tempPoint.x * arrPoints[i].y - tempPoint.y * arrPoints[i].x;
            tempPoint = arrPoints[i];
        }
        area = Math.abs(area / 2.0);
        
        return area;
    } 

'Coding > Math' 카테고리의 다른 글

홀수의 합으로 제곱근 구하기  (0) 2012.06.01
헤론의 공식  (2) 2011.08.30
원점을 중심으로 회전이동 시키는 공식  (2) 2008.12.20
Posted by chobocho

티스토리툴바