hdu 1828 (선분 트 리 + 스캐닝 라인 둘레 구하 기)
먼저, 둘레 를 구 하 는 사 고 를 소개 합 니 다. 왼쪽 에서 오른쪽으로 매번 한 변 을 삽입 한 후에 둘레 와 누적 값 = 새로 추 가 된 가로 + 새로 추 가 된 세로 변 을 소개 합 니 다.한 변 을 삽입 한 후에 새로 추 가 된 가로 변 의 나 무 는 구간 내 연속 선분 의 수 * 가로 변 의 길 이 를 추가 하고 새로 추 가 된 세로 변 은 앞 뒤 덮어 쓰 는 길이 의 차 이 를 삽입 하 는 것 과 같다 는 것 을 알 수 있다.한 줄 을 삽입 한 후, 사실은 이 사각형 에 대응 하 는 입 변 을 삭제 하 는 것 과 같다.불 연속 적 인 선분 이 나 타 났 다.가로 도 그 만큼 늘 었 다.이 생각 은 비교적 생각 하기 쉽다.
다음은 실 현 된 문제 입 니 다. 앞 뒤로 덮어 쓰 는 길이 의 가 치 를 구하 기 쉽 습 니 다. 스 캔 라인 템 플 릿 을 사용 하면 됩 니 다. 매번 삽입 한 후에 몇 개의 연속 적 인 라인 이 있 기 를 바 랍 니 다. 이것 이 바로 so low 구간 의 합병 이 아 닙 니까?
마지막 으로 주의 하 는 세부 사항 을 말씀 드 리 겠 습 니 다. 면적 을 구 하 는 과정 에서 모두 중복 되 는 값 을 없 애 지 않 았 을 수도 있 지만 여기 서 없 애 지 않 으 면 안 됩 니 다.우 리 는 연속 적 인 구간 개 수 는 반드시 세 개의 값 을 유지 해 야 한다 고 요구 합 니 다. 전체 구간 내 선분 의 개 수 는 왼쪽 이 덮 여 있 는 지, 오른쪽 이 덮 여 있 는 지 여부 입 니 다.예 를 들 어 한 구간 a 의 두 개의 하위 구간 은 b1 [10, 30], b2 [30, 30] 이다. 그러면 우 리 는 [10, 30] 을 삽입 할 때 b2 [10, 30] 를 덮 고 다른 구간 c [30, 40] 가 모두 덮 이면 a, c 의 전체 구간 의 선분 수 를 요구한다. 그 중 하 나 는 a 의 오른쪽 과 c 의 왼쪽 이 덮 여 있 는 지, 실제 상황 에서 a 의 오른쪽 이 덮 여 있 는 지 를 보 는 것 이다. 그러나 b2 라 는 점 이 업데이트 되 지 않 았 기 때문이다.그래서 덮 이지 않 으 면 문제 가 생 긴 다.이때 까지 건물 주 는 hdu 의 G + wa, c + a 를 건 네 주 었 습 니 다...구덩이 야!!!나중에 한 조 의 데이터 가 지나 갈 수 없다 는 것 을 발견 했다.
2
10 10 30 30
30 10 50 30
이 두 사각형 은 두 개의 변 이 완전히 겹 쳐 져 있다. 만약 에 우리 가 x 의 크기 만 정렬 하면 첫 번 째 사각형 의 아웃 사 이 드 를 계산 하고 둘레 에 20 을 더 한 다음 에 두 번 째 사각형 의 입 사 이 드 를 계산 하면 20 을 더 할 것 이다. 우 리 는 정렬 할 때 x 가 같 으 면 입 사 이 드 를 앞 에 놓는다.여러분 스스로 체험 하 실 수 있 습 니 다.아래 에 코드 를 동봉 합 니 다.
#include
#include
#include
#include
#include
using namespace std;
const int MAX=2*1e4+20;
int N;
int y[MAX];
int sum=0;
typedef struct{
int x,y1,y2;
int f;
void set(int xx,int yy1,int yy2,int ff)
{
x=xx;
y1=yy1;
y2=yy2;
f=ff;
}
}Node;
Node no[MAX];
typedef struct
{
int left,right;
int cover;
int realleft,realright,len;
int lflag,rflag,cnt;
void set(int l,int r)
{
lflag=rflag=cnt=0;
left=l;
right=r;
cover=0;
len=0;
realleft=y[l];
realright=y[r];
}
}P;
P per[4*MAX];
bool cmp(const Node &n1,const Node &n2)
{
if(n1.x!=n2.x)
return n1.xn2.f;
}
void build(int id,int left,int right)
{
per[id].set(left,right);
if(right-left==1)
return;
int mid=(left+right)/2;
build(id<<1,left,mid);
build(id<<1|1,mid,right);
}
void get_len(int t)
{
if(per[t].cover>0)
{
per[t].len=per[t].realright-per[t].realleft;
per[t].cnt=per[t].lflag=per[t].rflag=1;
}
else
if(per[t].left+1==per[t].right)
{
per[t].len=0;
per[t].cnt=per[t].lflag=per[t].rflag=0;
}
else
{
per[t].len=per[t<<1].len+per[t<<1|1].len;
per[t].lflag=per[t<<1].lflag;
per[t].rflag=per[t<<1|1].rflag;
per[t].cnt=per[t<<1].cnt+per[t<<1|1].cnt-per[t<<1].rflag*per[t<<1|1].lflag;
}
}
void update(int id,Node node)
{
if(per[id].realleft==node.y1&&per[id].realright==node.y2)
{
per[id].cover+=node.f;
get_len(id);
return;
}
if(per[id<<1].realright>=node.y2)
update(id<<1,node);
else
if(per[id<<1|1].realleft<=node.y1)
update(id<<1|1,node);
else
{
Node m=node;
m.y2=per[id<<1].realright;
update(id<<1,m);
m=node;
m.y1=per[id<<1|1].realleft;
update(id<<1|1,m);
}
get_len(id);
}
int main()
{
int x1,x2,y1,y2;
int num=1;
while(scanf("%d",&N)!=EOF)
{
memset(y,0,sizeof(y));
sum=0;
int t=0;
for(int i=0;i 좋은 웹페이지 즐겨찾기
