POJ - 1177 Picture (선분 트 리 + 스캐닝 라인)

2399 단어 데이터 구조
POJ - 1177 제목.
제목: 사각형 을 한 무더기 주 고 이 사각형 의 둘레 를 구하 라.
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define met(a,b) memset(a,b,sizeof(a))
const int maxn = 5010;
struct node
{
    int x,v,y1,y2;
    node(){}
    node(int a,int b,int c,int d)
    { x = a; v = b; y1 = c; y2 = d;}
}X[maxn<<1];
map id;
int y[maxn << 1],ylen[maxn << 1];
int cover[maxn<<3],len[maxn<<3],cnt[maxn<<3],flag[maxn<<1];
int xnum,ynum;
bool cmp(node a,node b)
{   return a.x < b.x;   }

void pre()
{
    id.clear();
    met(cover,0);   met(ylen,0);
//   
    sort(X, X + xnum, cmp);
    sort(y, y + ynum);
    ynum = unique(y,y+ynum) - y;

    for(int i = 0; i < ynum - 1; i++)
    {
        id[ y[i] ] = i + 1 ;
        ylen[i+1] = y[i+1] - y[i];
    }

    id[y [ynum-1] ] = ynum;
    ylen[ynum] = 0;
}
void up(int ul,int ur,int v,int id,int l,int r)
{
    if(r < ul || l > ur) return;
    if(l >= ul && r <= ur)
    {
        cover[id] += v;
        if(l == r)
        {
            if(cover[id])
            {
                len[id] = ylen[l]; cnt[id] = 1; flag[l] = 1; return;
            }
            else {len[id] = 0; cnt[id] = 0; flag[l] = 0; return;}
        }
    }
    int m = l+r>>1;
    if(ul <= m) up(ul,ur,v,id<<1,l,m);
    if(ur > m) up(ul,ur,v,id<<1|1,m+1,r);

    len[id] = len[id<<1] + len[id<<1|1];
    cnt[id] = cnt[id<<1] + cnt[id<<1|1];

    if(flag[m] && flag[m+1])
        cnt[id]--;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        xnum = 0, ynum = 0;
        for(int i = 0; i < n ; i++)
        {
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            X[xnum++] = node(a,1,b,d); X[xnum++] = node(c,-1,b,d);
            y[ynum++] = b, y[ynum++] = d;
        }
        pre();  //     

        int ret = 0; int last = 0,lastnum = 0;
        for(int i = 0; i < xnum; i++)
        {
            int id1 = id[X[i].y1] , id2 = id[X[i].y2];
            up(id1,id2-1,X[i].v,1,1,ynum);
            int th = abs(len[1]-last);
            if(i) th += lastnum*2*(X[i].x-X[i-1].x);
            lastnum = cnt[1];
            //cout<< th <
운동, 다이어트!MediaPipe로 글쓰기 헬스 프로그램을 만들어 봤습니다[PunchWriter ver0.1]
TIL ~ 2022-03-20-일

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage