글 읽기 - 예외 케이스를 도저히 못찾겠습니다...

minuk6219 5년 전 0

계속 틀렸습니다가 나오는데 어디서 틀렸는지 정말 모르겠어요..

도와주세요

#include<cstdio>
#include<vector>
using namespace std;

bool flag[1001];
vector<pair<int,int>> left_low[1001];
vector<pair<int,int>> right_high[1001];

vector<int> map[1001];

void dfs(int i);
int main(void)
{
	int N;
	int x1,x2,y1,y2;
	int x3,x4,y3,y4;
	int cnt = 0;
	bool chk = false;
	scanf("%d",&N);
	for(int i = 1; i <= N ; i++)
	{
		flag[i]=false;
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		if(((x1*x2 == 0 && y1*y2<=0) || (y1*y2 == 0 && x1*x2<=0)) && chk == false){ //원점을 지나는 직사각형이 하나라도 있으면
			chk = true;
			cnt=-1;
		}
		left_low[i].push_back(make_pair(x1,y1));
		right_high[i].push_back(make_pair(x2,y2));
	}

	for(int i = 1 ; i < N ; i++)
	{
		x1=left_low[i].front().first;
		y1=left_low[i].front().second;
		x2=right_high[i].front().first;
		y2=right_high[i].front().second;
		for(int j = i+1 ; j<= N ; j++){
				
			x3=left_low[j].front().first;
			y3=left_low[j].front().second;
			x4=right_high[j].front().first;
			y4=right_high[j].front().second;
			
			//x좌표를 기준으로 생각할거야.
			if(x1 < x3){ //두번째 사각형이 더 오른쪽에.
				if(y3 > y2 || x3 > x2) //절대 만날 수 없는경우
					continue;
				else {
					if(y3 < y1){
						if(y4 >= y1){
							//connected
							map[i].push_back(j);
							map[j].push_back(i);
						}
					}
					else if(y3 > y1){
						if(x4 >= x2 || y4 >= y2){
							//connected
							map[i].push_back(j);
							map[j].push_back(i);
						}
					}
					else{
						// always connected
						map[i].push_back(j);
						map[j].push_back(i);
					}
				}
			}
			else if(x3 < x1)
			{
				if(y4 < y1 || x4 < x1)
					continue;
				else {
					if(y1 < y3){
						if(y2 >= y3){
							//connected
							map[i].push_back(j);
							map[j].push_back(i);
						}
					}
					else if(y1 > y3){
						if(x2 >= x4 || y2 >= y4){
							//connected
							map[i].push_back(j);
							map[j].push_back(i);
						}
					}
					else{
						//connected
						map[i].push_back(j);
						map[j].push_back(i);	
					}
				}
			}
			else{	//x1 = x3인 경우 y에따라
				if(y3 > y2 || y1 > y4)
					continue;
				else{
					map[i].push_back(j);
					map[j].push_back(i);

				}
			}

		}
	}

	for(int i =1 ; i <= N ; i++)
	{
		if(flag[i] == false){
			cnt++;
			dfs(i);
		}
	}
	printf("%d\n",cnt);
	return 0;
}
void dfs(int x)
{
	flag[x] = true;
	for(int i = 0 ; i < map[x].size() ; i++)
	{
		int pos = map[x][i];
		if(flag[pos] == false)
		{
			dfs(pos);
		}
	}
}

sgchoi5 5년 전 0

CHCI 문제는 대회에서 사용했던 TC 가 공개되어 있습니다. 그걸로 한 번 해보셔요.

http://gooddaytocode.blogspot....

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

예외 케이스를 도저히 못찾겠습니다...

minuk6219 5년 전 0

sgchoi5 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말