poj 1177 Picture (선분 수 는 직사각형 둘레 와)
두 가지 방법 이 있 는 셈 이다.
1. 직접 분 산 된 후에 Y 축의 사각형 과 뒤의 선분 을 계산 한 다음 에 X 축 을 계산한다.이것 은 바로 한 라인 을 삽입 하고 한 라인 을 삭제 하 는 것 입 니 다. 코드 가 비교적 깁 니 다.
2. 진 홍 WC 99 논문 인 은 너무 길 어서 잘 이해 하지 못 했다.그러나 인터넷 에서 이 문제 의 문 제 를 찾 아 대충 알 아 보 았 다.
내 가 이런 방법 에 대한 이 해 를 말 해 볼 게, 비교적 물...
이 문제 의 선분 트 리 는 여러 도 메 인 을 업데이트 해 야 합 니 다.제 코드 에 있어 Tnode (즉, 제 라인 트 리 노드) 중의:
1. l, r 는 평소 선분 나무 와 마찬가지 로 분 산 된 다음 에 표 시 됩 니 다.
2. len, 현재 노드 의 하위 트 리 에 덮 인 선의 길이.
3. num, 서브 트 리 에서 몇 단락 으로 나 뉘 는데 이것 은 주로 X 축 과 평행 하 는 선분 의 길 이 를 계산 하기 위 한 것 이다.
4. cover, 현재 노드 가 덮어 쓸 지 여 부 를 표시 합 니 다.
5. rb lb 는 현재 노드 의 오른쪽 점 과 왼쪽 점 이 덮어 쓸 지 여 부 를 표시 합 니 다.num 의 수량 을 찾 으 려 면 필요 합 니 다.
Sline 구조 체 는 스캐닝 라인 입 니 다. 그 중의 flag 표 시 는 입 변 입 니까? 나 갑 니까?
구체 적 인 과정: 전기 처리 과정 과 사각형 의 면적 은 별 차이 가 없다 (그렇지 않 으 면 먼저 그것 을 배 워 야 한다. 그것 은 훨씬 간단 하 다 = =). 관건 은 선분 나무의 상역 의 갱신 이다. num 을 갱신 할 때 주의해 야 한다. 만약 에 두 선분 이 연결 되 어 있다 면 1 (rb 와 lb 로 판단 할 수 있다) 을 줄 여야 한다. 이 len 은 현재 의 총 길이 이기 때문에 선분 의 길 이 를 구 할 때현재 총 길이 에서 업데이트 전의 총 길이 (절대 값) 를 빼 야 합 니 다. 즉, 이번 스 캔 라인 후의 길이 입 니 다.
응.대충 이 해 를 많이 했 어 요. 선분 나무 가 너무 많이 변형 됐어 요. 엉엉..................................................책임 은 무 겁 고 갈 길 은 멀다!!
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#define MID(x,y) ((x+y)>>1)
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define BUG printf("here!!!
");
using namespace std;
const int MAX = 5010;
struct Tnode{ int l,r,num,len,cover;bool lb,rb;};
struct Sline{ int x,y1,y2,flag;};
Tnode node[MAX<<2];
Sline l[MAX<<1];
int y[MAX<<1];
void add_line(int x1,int y1,int x2,int y2,int &cnt)
{
l[cnt].x = x1; l[cnt].y1 = y1; l[cnt].y2 = y2; l[cnt].flag = 1;
y[cnt++] = y1;
l[cnt].x = x2; l[cnt].y1 = y1; l[cnt].y2 = y2; l[cnt].flag = -1;
y[cnt++] = y2;
}
void init()
{
memset(node,0,sizeof(node));
}
void Build(int t,int l,int r)
{
node[t].l = l; node[t].r = r;
node[t].num = 0;
if( l == r - 1 ) return ;
int mid = MID(l,r);
Build(R(t),mid,r);
Build(L(t),l,mid);
}
void Updata_len(int t)
{
if( node[t].cover > 0 )
{
node[t].num = node[t].lb = node[t].rb = 1;
node[t].len = y[node[t].r] - y[node[t].l];
}
else
if( node[t].l == node[t].r - 1 )
node[t].rb = node[t].lb = node[t].len = node[t].num = 0;
else
{
node[t].rb = node[R(t)].rb; node[t].lb = node[L(t)].lb;
node[t].len = node[L(t)].len + node[R(t)].len;
node[t].num = node[L(t)].num + node[R(t)].num - node[R(t)].lb*node[L(t)].rb;
} // , 。。
}
void Updata(int t,Sline p)
{
if( y[node[t].l] >= p.y1 && y[node[t].r] <= p.y2 )
{
node[t].cover += p.flag;
Updata_len(t);
return ;
}
if( node[t].l == node[t].r - 1 ) return ;
int mid = MID(node[t].l ,node[t].r);
if( p.y1 <= y[mid] ) Updata(L(t),p);
if( p.y2 > y[mid] ) Updata(R(t),p);
Updata_len(t);
}
int solve(int n,int cnt,Sline *l)
{
init();
Build(1,0,cnt-1);
int ans = 0,last = 0,lines = 0;
for(int i=0; i<n; i++)
{
Updata(1,l[i]);
if( i >= 1 )
ans += 2 * lines * (l[i].x - l[i-1].x);// x
ans += abs(node[1].len - last); // y
last = node[1].len;
lines = node[1].num;
}
return ans;
}
bool cmp(Sline a,Sline b)
{
if( a.x == b.x ) return a.flag > b.flag;
return a.x < b.x;
}
int main()
{
int n,x1,x2,y1,y2;
while( ~scanf("%d",&n) )
{
if( n == 0 )
{
printf("0
");
continue;
}
int cnt = 0;
for(int i=0; i<n; i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
add_line(x1,y1,x2,y2,cnt);
}
sort(y,y+cnt);
sort(l,l+cnt,cmp);
int t = cnt;
t = unique(y,y+cnt) - y;
int ans = solve(cnt,t,l);
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.