poj 1177 구간 트 리 직사각형 둘레 및
2071 단어 데이터 구조
평면 에 약간의 직사각형 을 주어 그것들의 둘레 와 길 이 를 구하 다.
분석:
구간 트 리 로 x 축 상단 구간 의 덮어 쓰기 속성 을 유지 합 니 다.구간 트 리 는 일부 구간 의 성질 을 유지 하고 구 조 는 build (l, mid), build (mid, r), 선분 트 리 는 일부 점 의 성질 을 유지 하 며 구 조 는 build (l, mid), build (mid + 1, r) 이다.구간 나 무 는 흔히 선분 나무 로 여 겨 지지 만 개인 적 으로 점선 이 구분 되 어 있 기 때문에 문 제 를 고려 할 때 그들 을 구별 하 는 것 이 좋다 고 생각 합 니 다. 비록 그들의 핵심 사상 은 레이 지 와 같 지만.
코드:
//poj 1177
//sep9
#include
#include
using namespace std;
const int MAXN=10012;
int n;
struct LINE
{
int y,x1,x2;
int f;
}line[MAXN];
struct Node
{
int l,r;
int cnt;//lenth
int lf,rf;//actual left/right endpoint
int numseg;//branch number
int c;//cover
bool lcover,rcover;
}segTree[MAXN*4];
int x[MAXN];
bool cmp(LINE a,LINE b)
{
return a.y0){
segTree[i].cnt=segTree[i].rf-segTree[i].lf;
segTree[i].numseg=1;
segTree[i].lcover=segTree[i].rcover=true;
return;
}
if(segTree[i].l+1==segTree[i].r){
segTree[i].cnt=0;
segTree[i].numseg=0;
segTree[i].lcover=segTree[i].rcover=false;
}else{
segTree[i].cnt=segTree[i*2].cnt+segTree[i*2+1].cnt;
segTree[i].lcover=segTree[i*2].lcover;
segTree[i].rcover=segTree[i*2+1].rcover;
segTree[i].numseg=segTree[i*2].numseg+segTree[i*2+1].numseg;
if(segTree[i*2].rcover&&segTree[i*2+1].lcover) --segTree[i].numseg;
}
}
void update(int i,LINE e)
{
if(segTree[i].lf==e.x1&&segTree[i].rf==e.x2){
segTree[i].c+=e.f;
pushUp(i);
return ;
}
if(e.x2<=segTree[i*2].rf) update(i*2,e);
else if(e.x1>=segTree[i*2+1].lf) update(i*2+1,e);
else{
LINE tmp=e;
tmp.x2=segTree[i*2].rf;
update(i*2,tmp);
tmp=e;
tmp.x1=segTree[i*2+1].lf;
update(i*2+1,tmp);
}
pushUp(i);
}
int main()
{
scanf("%d",&n);
int t=0;
for(int i=0;i 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
