hdu 1828 Picture (선분 수 는 직사각형 둘레 와)

- > 제목 은 여기에 찍 어 주세요 < -
제목
제목 분석: 직사각형 둘레 와.이 문 제 를 보고 요 며칠 동안 쓴 사각형 의 면적 과 차이 가 많 지 않다 고 생각 한 후에 바로 선분 나무 + 스캐닝 선 을 두 드 렸 다. 쓰기 차이 가 많 지 않 아서 야 면적 과 차이 가 있다 는 것 을 알 게 되 었 다.그 다음 에 면적 을 합 치 는 방법 을 모방 하여 선분 나무 노드 에 각종 정 보 를 넣 으 면 결 과 는 항상 옳지 않다.다시 한 번 생각 을 정리 해 보면 둘레 를 구하 고 두 가지 상황 만 고려 해 야 한다. 수평 의 변 과 수직 의 변, 수평 의 변 은 구하 기 어렵 지 않다. 한 개의 스캐닝 라인 을 삽입 할 때마다 결 제 를 한다. 현재 구간 은 몇 단락 으로 나 뉘 어 져 있 고 분 리 된 단수 * 2 * 현재 스캐닝 라인 과 앞의 스캐닝 라인 x 방향의 차 이 는 바로 이 구간 의 수평 방향 에서 둘레 이다.현재 구간 이 몇 단락 으로 나 뉘 었 는 지 기록 하려 면 각 노드 에 2 개의 변 수 를 추가 해 야 합 니 다. r 는 현재 구간 이 왼쪽 연속 인지 오른쪽 연속 인지 각각 표시 합 니 다.세로 방향 에 있 는 둘레 선 도 좋 습 니 다. 삽 입 된 라인 이 현재 구간 을 덮어 쓰 는 횟수 를 1 에서 0 으로 바 꾸 면 이 길 이 는 오른쪽 경계 이 고 현재 구간 의 덮어 쓰 는 횟수 를 0 에서 1 로 바 꾸 면 이 길 이 는 왼쪽 경계 입 니 다.이 사고방식 에 따라 쓰 려 면 현재 구간 이 덮어 쓰 지 않 은 길이 와 마침 덮어 쓰 지 않 은 길 이 를 기록 해 야 한다. 그러나 이렇게 쓰 려 면 계속 쓰 지 않 고 과감하게 다시 한 번 썼 다. 다시 쓸 때 이렇게 하 는 것 은 너무 번 거 로 운 것 을 발견 했다. 우 리 는 현재 구간 의 총 길 이 를 직접 통계 할 수 있 고, 동시에 상 태 를 기록 할 때 구간 의 총 길 이 를 기록 할 수 있다.그러면 이 2 차 구간 의 총 길이 차 의 절대 치 는 현재 스캐닝 라인 을 삽입 한 후 총 구간 에 새로 생 성 되 거나 사라 진 라인, 즉 둘레 의 왼쪽 경계 나 오른쪽 경계 이다.이렇게 생각하면 훨씬 쓰기 쉽다.그러나 또 하나의 문 제 는 두 개의 스캐닝 라인 의 x 가 같다 면 우 리 는 먼저 사각형 왼쪽 경계 의 스캐닝 라인 을 삽입 해 야 한다. 이 두 개의 선 이 겹 치기 때문에 먼저 사각형 오른쪽 경계 의 스캐닝 라인 을 삽입 하면 겹 치 는 변 은 계산 되 지만 사실은 계산 할 수 없다. 이것 은 내 코드 뒤의 마지막 테스트 데 이 터 를 보면 알 수 있다.
자세 한 내용 은 코드 를 보십시오.
4. 567913. 후기: 이 문 제 는 어렵 지 않 지만 이렇게 오래 썼 는데 주로 너무 고 집 스 러 워 서 오랫동안 조정 하지 않 았 으 면 생각 을 빨리 정리 하고 다시 써 야 한다.그리고 사유의 정세 에 빠 져 서 는 안 된다. 이 문 제 는 직사각형 면적 과 다르다.