글 읽기 - 1355 구멍난케이크 자르기 예외를 모르겠네요 ㅜㅜ

qkrcjdgh1004 8년 전 0

처음엔 그래프로 하다가 좋은 조언을 받아서 사각형을 나눈 다음 작은 사각형 안에 만들어지는 사각형 개수를 뺴는 방식으로 하고 있는데 답 다 잘 나오는거 같은데 도저히 예외를 모르겠네요 ㅜㅜ 문제 푸신 분들이 많이 없으시지만 그래도 조언을 얻을 수 있을까 해서 올려봅니다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int cs, hs, hn, vn, h[51], v[51];


int main(){
    scanf("%d %d", &cs, &hs);
    scanf("%d", &hn);
    if(hn != 0) for(int i = 0; i < hn; i++) scanf("%d", &h[i]);
    scanf("%d", &vn);
    if(vn != 0) for(int i = 0; i < vn; i++) scanf("%d", &v[i]);
    /* 사각형에 포함되지 않은 직선 없애기 */
    int temp_hn = hn, temp_vn = vn;
    for(int i = 0; i < temp_hn; i++) if(!(-cs < h[i] && h[i] < cs)) { h[i] = 1004; hn--; }
    for(int i = 0; i < temp_vn; i++) if(!(-cs < v[i] && v[i] < cs)) { v[i] = 1004; vn--; }
    sort(h, h+hn);
    sort(v, v+vn);
    for(int i = 1; i < temp_hn; i++) if(h[i-1] == h[i] && h[i] != 1004) { h[i] = 1004; hn--; }
    for(int i = 1; i < temp_vn; i++) if(v[i-1] == v[i] && v[i] != 1004) { v[i] = 1004; vn--; }
    sort(h, h+hn);
    sort(v, v+vn);
    int res = (hn+1)*(vn+1);
//    printf("%d %d %d\n", hn, vn, res);
    /* 구멍 안에 사각형 있는지 판별 */
    for(int i = 1; i < hn; i++) {
        if ((-hs <= h[i-1] && h[i-1] <= hs) && (-hs <= h[i] && h[i] <= hs)) {
            for(int j = 1; j < vn; j++){
                if ((-hs <= v[j-1] && v[j-1] <= hs) && (-hs <= v[j] && v[j] <= hs)) {
                    res--;
                }
            }
        }
    }
    printf("%d", res);
    return 0;
}

portableangel 8년 전 2

입력으로는

5 3

2 3 4

입니다.

5조각이 나와야 하는데 코드 돌려보니 4조각이 나오네요

는 놋북사고 누워서 코딩하는게 편해서 컴실을 한동안 안갔네 ㅠㅠ 낼부턴 매일감

qkrcjdgh1004 8년 전 0

이거 처리하니깐 11%까지 맞네요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

하하 그래도 기쁘당..

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int cs, hs, hn, vn, h[51], v[51];


int main(){
    scanf("%d %d", &cs, &hs);
    scanf("%d", &hn);
    if(hn != 0) for(int i = 0; i < hn; i++) scanf("%d", &h[i]);
    scanf("%d", &vn);
    if(vn != 0) for(int i = 0; i < vn; i++) scanf("%d", &v[i]);
    /* 사각형에 포함되지 않은 직선 없애기 */
    int temp_hn = hn, temp_vn = vn;
    for(int i = 0; i < temp_hn; i++) if(!(-cs < h[i] && h[i] < cs)) { h[i] = 1004; hn--; }
    for(int i = 0; i < temp_vn; i++) if(!(-cs < v[i] && v[i] < cs)) { v[i] = 1004; vn--; }
    sort(h, h+hn);
    sort(v, v+vn);
    /* 같은 직선 없애기 */
    for(int i = 1; i < temp_hn; i++) if(h[i-1] == h[i] && h[i] != 1004) { h[i] = 1004; hn--; }
    for(int i = 1; i < temp_vn; i++) if(v[i-1] == v[i] && v[i] != 1004) { v[i] = 1004; vn--; }
    sort(h, h+hn);
    sort(v, v+vn);
    int res = (hn+1)*(vn+1);
    //printf("%d %d %d\n", hn, vn, res);
    
    /* 작은 사각형 을 직선 두개가 나누는지 판별 */
    for(int i = 1; i < hn; i++)
        if((-hs <= h[i-1] && h[i-1] <= hs) && (-hs <= h[i] && h[i] <= hs))
            res++;
    for(int i = 1; i < vn; i++)
        if((-hs <= v[i-1] && v[i-1] <= hs) && (-hs <= v[i] && v[i] <= hs))
            res++;
    
    /* 구멍 안에 사각형 있는지 판별 */
    for(int i = 1; i < hn; i++) {
        if ((-hs <= h[i-1] && h[i-1] <= hs) && (-hs <= h[i] && h[i] <= hs)) {
            for(int j = 1; j < vn; j++){
                if ((-hs <= v[j-1] && v[j-1] <= hs) && (-hs <= v[j] && v[j] <= hs)) {
                    res--;
                }
            }
        }
    }
    printf("%d", res);
    return 0;
}

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

문제

문제

출처

ICPC

1355 구멍난케이크 자르기 예외를 모르겠네요 ㅜㅜ

qkrcjdgh1004 8년 전 0

portableangel 8년 전 2

qkrcjdgh1004 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말