ZOJ3273 POJ3832 HDU3265 Posters
데이터 범위 가 크 지 않 고 정수 이기 때문에 이산 화 할 필요 가 없다.알고리즘 사상 은 왼쪽 에서 오른쪽으로 스 캔 하고 node. length 는 전체 Y 축 이 사용 할 수 있 는 길이 입 니 다.LINE 의 flag 는 사각형 의 왼쪽 과 오른쪽 을 기록 하 는 데 사 용 됩 니 다. 왼쪽 은 1 입 니 다. node 에 들 어가 면 LINE 의 Y 축 에 있 는 이 부분 을 사용 할 수 있 습 니 다. 오른쪽 은 - 1 입 니 다. node 에 들 어가 면 LINE 의 Y 축 에 있 는 이 부분 을 사용 할 수 없습니다.이것 은 그림 을 그 려 야만 이해 할 수 있다.
/*******************************************************************************
# Author : Neo Fung
# Email : [email protected]
# Last modified: 2012-01-18 20:11
# Filename: HDU1689 Just a Hook.cpp
# Description :
******************************************************************************/
#ifdef _MSC_VER
#define DEBUG
#endif
#include <fstream>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <functional>
#include <ctype.h>
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MAX 200010
using namespace std;
struct NODE
{
int l,r,length,cover;
}node[MAX*4];
struct LINE
{
int x,y1,y2,flag;
}line[MAX*2];
int y_coord[MAX*2];
void add_line(const int &x1,const int &x2,const int &y1,const int &y2,int &cnt)
{
line[cnt].x=x1;
line[cnt].y1=y1;
line[cnt].y2=y2;
line[cnt++].flag=1;
line[cnt].x=x2;
line[cnt].y1=y1;
line[cnt].y2=y2;
line[cnt++].flag=-1;
}
bool inline cmp(const LINE &lhs,const LINE &rhs)
{
return lhs.x<rhs.x;
}
void init()
{
memset(node,0,sizeof(node));
}
void build(const int &t,const int &l,const int &r)
{
node[t].l=l;
node[t].r=r;
if(l==r-1)
return;
int mid=(l+r)>>1;
build(L(t),l,mid);
build(R(t),mid,r);
}
void len(const int &t)
{
if(node[t].cover>0)
node[t].length = y_coord[node[t].r]-y_coord[node[t].l];
else if(node[t].l==node[t].r-1)
node[t].length=0;
else
node[t].length = node[R(t)].length+node[L(t)].length;
}
void update(const int &t,const LINE &lne)
{
if(y_coord[node[t].l]>=lne.y1 && y_coord[node[t].r]<=lne.y2)
{
node[t].cover+=lne.flag;
len(t);
return;
}
if(node[t].l==node[t].r-1) return;
int mid = (node[t].l+node[t].r)>>1;
if(lne.y1<=y_coord[mid])
update(L(t),lne);
if(lne.y2>y_coord[mid])
update(R(t),lne);
len(t);
}
__int64 solve(const int &n,const int &cnt)
{
init();
build(1,0,cnt-1);
update(1,line[0]);
__int64 sum=0ll;
for(int i=1;i<n;++i)
{
sum+=(line[i].x-line[i-1].x)*1ll*node[1].length;
update(1,line[i]);
}
return sum;
}
int main(void)
{
#ifdef DEBUG
freopen("../stdin.txt","r",stdin);
freopen("../stdout.txt","w",stdout);
#endif
int n;
int x1,y1,x2,y2,x3,y3,x4,y4;
while(scanf("%d",&n) && n)
{
int cnt=0,y_cnt=0;
for(int i=0;i<n;++i)
{
scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
add_line(x1,x3,y1,y2,cnt);
add_line(x3,x4,y1,y3,cnt);
add_line(x3,x4,y4,y2,cnt);
add_line(x4,x2,y1,y2,cnt);
y_coord[y_cnt++]=y1;
y_coord[y_cnt++]=y2;
y_coord[y_cnt++]=y3;
y_coord[y_cnt++]=y4;
}
sort(line,line+cnt,cmp);
sort(y_coord,y_coord+y_cnt);
y_cnt=unique(y_coord,y_coord+y_cnt)-y_coord;
printf("%I64d
",solve(cnt,y_cnt));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.