U E D R , A S I H C RSS
ZeroWiki

2002년도ACM문제샘플풀이/문제A



[edit]

1. 상규, 재동

  • 첫번째 풀때가 1시간쯤 걸렸고 2번째 풀때는 35분쯤 걸렸습니다. 두번째 풀때는 전보다 좋은 알고리즘이 떠올랐습니다.

~cpp 
#include <iostream>
using namespace std;

struct POINT
{
	int x, y;
};

int numOfData;
POINT inputData[10][4];
int outputData[10];

#define max(a,b) (a > b) ? a : b
#define min(a,b) (a < b) ? a : b

void input()
{
	cin >> numOfData;
	for(int i=0;i<numOfData;i++)
	{
		for(int j=0;j<4;j++)
		{
			cin >> inputData[i][j].x;
			cin >> inputData[i][j].y;
		}
	}
}

void process()
{
	POINT maxPoint, minPoint;
	int overlappedRect;
	for(int i=0;i<numOfData;i++) {
		maxPoint.x = max(inputData[i][0].x,inputData[i][2].x);
		maxPoint.y = max(inputData[i][0].y,inputData[i][2].y);

		minPoint.x = min(inputData[i][1].x,inputData[i][3].x);
		minPoint.y = min(inputData[i][1].y,inputData[i][3].y);

		overlappedRect = (minPoint.x - maxPoint.x) * (minPoint.y - maxPoint.y);
		if(overlappedRect < 0) overlappedRect = 0;
		
		outputData[i] = (inputData[i][1].x - inputData[i][0].x) * (inputData[i][1].y - inputData[i][0].y);

		outputData[i] -= overlappedRect;
	}
}

void output()
{
	for(int i=0;i<numOfData;i++)
	{
		cout << outputData[i] << endl;
	}
}

void main()
{
	input();
	process();
	output();
}
[edit]

2. 인수

  • 한 두시간은 걸린거 같다; 문제를 제대로 읽어보지 않은 탓이다. 무슨 찌그러진 사각형을 생각하다니; 미친거 아닌가 모르겠다.
  • 이건 시간 생각안하고, 열심히 디자인 해볼라고 노력했는데.. 아무래도 경시대회에선 별루 좋은 방법 같진 않다. 속도 높이는데 중점을 둬야겠다.

~cpp 
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

struct Point
{
	int x;
	int y;
	Point(int arg_x, int arg_y)
	{
		x = arg_x;
		y = arg_y;
	}
};

class Line
{
public :
	int x1;
	int y1;
	int x2;
	int y2;

	bool IsVertical()
	{
		return x1 == x2;
	}

	bool IsHorizontal()
	{
		return y1 == y2;
	}

	bool IsSameVerticalLine(Line& line)
	{
		return line.x1 == x1;
	}

	bool IsSameHorizontalLine(Line& line)
	{
		return line.y1 == y1;
	}

	Line() {}

	Line(int arg_x1, int arg_y1, int arg_x2, int arg_y2) 
		: x1(arg_x1), y1(arg_y1), x2(arg_x2), y2(arg_y2) {}

	bool IsHorizontalCrossVertical(Line& line)
	{
		return line.y1 >= y1 && line.y1 <= y2 && x1 >= line.x1 && x1 <= line.x2;
	}
	
	bool IsVerticalCrossHorizontal(Line& line)
	{
		return line.x1 >= x1 && line.x1 <= x2 && y1 >= line.y1 && y1 <= line.y2;
	}

	bool IsMeet(Line& line)
	{
		if(IsVertical())
		{
			if( IsSameVerticalLine(line) || IsHorizontalCrossVertical(line) )
				return true;
			return false;
		}
		else
		{
			if( IsSameHorizontalLine(line) || IsVerticalCrossHorizontal(line) )
				return true;
			return false;
		}
		return false;
	}
};

class Rect
{
public :
	int x1;
	int y1;
	int x2;
	int y2;
	vector<Point> intersections;

	Line GenerateLine(int nth)
	{
		switch(nth)
		{
		case 0:
			return Line(x1, y1, x2, y1);
		case 1:
			return Line(x2, y1, x2, y2);
		case 2:
			return Line(x1, y2, x2, y2);
		case 3:
			return Line(x1, y1, x1, y2);
		default:
			return Line(x1, y1, x1, y1);
		}
	}

	bool IsHeapUp()
	{
		return intersections.size() == 2;
	}

	bool IsSmallerThan(Rect& rect)
	{
		return rect.x2 >= x2;
	}

	void AddIntersectionPoint(Line& rect1Line, Line& rect2Line)
	{
		if(rect1Line.IsVertical())		
			intersections.push_back( Point(rect1Line.x1, rect2Line.y1) );
		else
			intersections.push_back( Point(rect2Line.x1, rect1Line.y1) );
	}

	Rect(int arg_x1, int arg_y1, int arg_x2, int arg_y2) 
		: x1(arg_x1), y1(arg_y1), x2(arg_x2), y2(arg_y2) {}

	void CountIntersectionPoint(Rect& rect)
	{
		Line rect1Line, rect2Line;
		for(int i = 0 ; i < 4 ; ++i)
		{
			rect1Line = GenerateLine(i);
			for(int j = 0 ; j < 4 ; ++j)
			{
				rect2Line = rect.GenerateLine(j);
				if( rect1Line.IsMeet(rect2Line) )
				{
					AddIntersectionPoint(rect1Line, rect2Line);					
				}
			}
		}
	}

	int GetRestSquare(Rect& rect)
	{
		int intersectionSquare = 0;
		if( IsHeapUp() )	
		{
			intersectionSquare = abs(intersections[1].x - intersections[0].x)
									* abs(intersections[1].y - intersections[0].y);
		}
		else
		{
			if( IsSmallerThan(rect) )
				intersectionSquare = (x2-x1) * (y2-y1);
			else 
				intersectionSquare = (rect.x2-rect.x1) * (rect.y2-rect.y1);
		}
		return (x2-x1) * (y2-y1) - intersectionSquare;
	}
};

int main()
{
	Rect rect1(2,2,4,4);
	Rect rect2(1,1,5,5);
	rect1.CountIntersectionPoint(rect2);

	cout << rect1.GetRestSquare(rect2);	
	
	return 0;
}

[edit]

3. 창섭

  • 으흐.. 마지막에 이렇게 기가 막힌 알고리즘을 왜 생각지 못했을까 하며 통탄했었다. 아직 A 만 풀었지만.. C++ 이라고는 하지만 사실항 C 인거 같다.쩝.. 아무튼 내가 짜고도 알고리즘의 간단함에 놀라움을 금치 못했다. 다만 엄청난 삽질을 하고서 생각났다는게 어안이 벙벙할 뿐이다. 다른거 생각하기 귀찮아서 전부 전역변수로 넣어버린 것도 부끄럽다.
  • STL 을 공부해둘 걸 하는 후회가 있다. 배열을 쓸 때마다 느끼는 바다...쩝.


~cpp 
#include <iostream>
using namespace std;

void input();
int board1Size();
int calDiffSize();
void output();
int jdValue(int a, int b);
void sort(int a[], int size);
int num;
int board1[10];
int diffSize[10];
int x1, x2, x3, x4, y1, y2, y3, y4;

int main()
{
	input();
	board1Size();
	output();
	return 0;
}

void input()
{
	cin >> num;
	for (int i = 0; i < num; i++)
	{
		cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
		diffSize[i] = calDiffSize();
		board1[i] = board1Size();
	}
}

int board1Size()
{
	return (x2 - x1)*(y2 - y1);
}

int calDiffSize()
{
	int diffSize;
	if (x2 <= x3 || x1 >= x4 || y1 >= y4 || y2 <= y3)
		return 0;
	int x[4] = {x1, x2, x3, x4};
	int y[4] = {y1, y2, y3, y4};
	sort(x, 4);
	sort(y, 4);
	diffSize = jdValue(x[1], x[2]) * jdValue(y[1], y[2]);
	return diffSize;
}

void output()
{
	for (int i = 0; i < num; i++)
		cout << board1[i] - diffSize[i] <<endl;
}

int jdValue(int a, int b)
{
	if (a > b)
		return b - a;
	return a - b;
}

void sort(int a[], int size)
{
	for (int k = 0; k < size; k++)
	{
		for (int i = 0; i < size - 1; i++)
		{
			if (a[i] > a[i+1])
			{
				int temp;
				temp = a[i];
				a[i] = a[i+1];
				a[i+1] = temp;
			}
		}
	}
}
// sort 함수는 #include <algorithm> 한다음
// sort(&a[0], &a[size]); 하면 끝남
// 그리구 jdValue 이거는 절대값 구하는 함수 같은데
// 저것도 #include <cmath> 한다음, abs(값) 하면 끝남
[edit]

3.1. 상민(neocoin)

하고 보니 영역 체크가 없군요. ;; 뭐, 예제만 통과할려고 했네요. 앗차 위의 소스들을 보니 max, min이 있었지요. 다음에는 까먹지 말아야지..
~cpp 
#include <iostream>
#include <vector>
using namespace std;

struct DataSet{
	int underX[2];
	int underY[2];
	int upperX[2];
	int upperY[2];
};

vector< DataSet > datas;

void input(){
	int numberOfTestCase =0;
	cin >> numberOfTestCase;

	for ( int testCaseNum=0;testCaseNum<numberOfTestCase;testCaseNum++){
		DataSet data;
		for ( int i =0;i<2;i++)
			cin >> data.underX[i] >> data.underY[i];			
		
		for ( i =0;i<2;i++)
			cin >> data.upperX[i] >> data.upperY[i];
		
		datas.push_back(data);		
	}	
}

int getVisibleArea(DataSet& data){	
	int underArea = ( data.underX[1] - data.underX[0] ) * (data.underY[1]-data.underY[0]);
	int x[2];
	int y[2];
	
	x[0] = ( data.underX[0] > data.upperX[0] )?data.underX[0]:data.upperX[0];
	x[1] = ( data.underX[1] < data.upperX[1] )?data.underX[1]:data.upperX[1];
	y[0] = ( data.underY[0] > data.upperY[0] )?data.underY[0]:data.upperY[0];
	y[1] = ( data.underY[1] < data.upperY[1] )?data.underY[1]:data.upperY[1];

	int overArea = (x[1] - x[0])*(y[1]-y[0]);
	return underArea - overArea;
	
}
void process(){		
	vector<DataSet>::iterator iter;
	for ( iter = datas.begin(); iter != datas.end(); iter++)
		cout << getVisibleArea(*iter) << endl;
}
int main(){
	input();
	process();	
	return 0;
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:09
Processing time 0.0321 sec