POJ 151(선분 수+스캐닝 라인 은 직사각형 면적 을 구 합 니 다)
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int N = 10005;
struct node
{
int l,r;
int cov;
double len;
};
struct line
{
double x;
double y1;
double y2;
int f;
bool operator < (const line &a) const
{
return x < a.x;
}
};
class SegTree
{
private:
node tree[N];
double num[N];
int ncount;
public:
SegTree(double a[],int n)
{
for(int i=0;i<n;i++)
num[i] = a[i];
ncount = n;
Build(0,n-1,1);
}
void Build(int l,int r,int rt)
{
tree[rt].l = l;
tree[rt].r = r;
tree[rt].cov = 0;
tree[rt].len = 0;
if(l+1 == r) return;
int mid = (l+r)>>1;
Build(l,mid,2*rt);
Build(mid,r,2*rt+1);
}
void Insert(int l,int r,int p)
{
if(tree[p].l == l && tree[p].r == r)
{
tree[p].cov++;
tree[p].len = num[r] - num[l];
return;
}
int mid = (tree[p].l + tree[p].r)>>1;
if(r <= mid)
Insert(l,r,2*p);
else if(l >= mid)
Insert(l,r,2*p+1);
else
{
Insert(l,mid,2*p);
Insert(mid,r,2*p+1);
}
if(tree[p].cov == 0)
tree[p].len = tree[2*p].len + tree[2*p+1].len;
}
void Delete(int l,int r,int p)
{
if(tree[p].l == l && tree[p].r == r)
{
tree[p].cov--;
if(tree[p].cov <= 0)
{
if(tree[p].l+1 < tree[p].r)
tree[p].len = tree[2*p].len + tree[2*p+1].len;
else
tree[p].len = 0;
}
return;
}
int mid = (tree[p].l + tree[p].r)>>1;
if(r <= mid)
Delete(l,r,2*p);
else if(l >= mid)
Delete(l,r,2*p+1);
else
{
Delete(l,mid,2*p);
Delete(mid,r,2*p+1);
}
if(tree[p].cov == 0)
tree[p].len = tree[2*p].len + tree[2*p+1].len;
}
double getLen()
{
return tree[1].len;
}
};
int main()
{
int test=0,n;
double x1,y1,x2,y2;
double yval[N];
line data[N];
while(~scanf("%d",&n))
{
if(n==0) break;
test++;
int l1 = 0;
int l2 = 0;
for(int i=0;i<n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
yval[l1++] = y1;
yval[l1++] = y2;
data[l2].x = x1;
data[l2].y1 = y1;
data[l2].y2 = y2;
data[l2].f = -1;
l2++;
data[l2].x = x2;
data[l2].y1 = y1;
data[l2].y2 = y2;
data[l2].f = 1;
l2++;
}
sort(yval,yval+l1);
sort(data,data+l2);
l1 = unique(yval,yval+l1) - yval;
double sum = 0;
SegTree stree(yval,l1);
for(int i=0;i<l2-1;i++)
{
int l,r;
l = lower_bound(yval,yval+l1,data[i].y1) - yval;
r = lower_bound(yval,yval+l1,data[i].y2) - yval;
if(data[i].f == -1)
stree.Insert(l,r,1);
else
stree.Delete(l,r,1);
sum += stree.getLen() * (data[i+1].x - data[i].x);
}
printf("Test case #%d
", test);
printf("Total explored area: ");
printf("%.2lf
", sum);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.