题意很简单,但是周长并比面积并又稍微麻烦了一些
这时候要开一个numseg存储竖边的个数。
再开lbd,rbd分别表示边界,这样是为了帮助删除重合的边
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 22222
#define MAXM 104444
#define INF 100000000
#define eps 1e-7
#define L(X) X<<1
#define R(X) X<<1|1
using namespace std;
struct Seg
{
int l, r, h, s;
Seg(){}
Seg(int a, int b, int c, int d){l = a; r = b; h = c; s = d;}
bool operator <(const Seg &cmp) const{
if(h == cmp.h) return s > cmp.s;
return h < cmp.h;
}
}seg[MAXN];
struct node
{
int left, right, mid;
int len, cnt, numseg;
bool lbd, rbd;
}tree[4 * MAXN];
void up(int C)
{
if(tree[C].cnt)
{
tree[C].lbd = tree[C].rbd = 1;
tree[C].len = tree[C].right - tree[C].left + 1;
tree[C].numseg = 2;
}
else if(tree[C].left == tree[C].right)
tree[C].len = tree[C].numseg = tree[C].lbd = tree[C].rbd = 0;
else
{
tree[C].lbd = tree[L(C)].lbd;
tree[C].rbd = tree[R(C)].rbd;
tree[C].len = tree[L(C)].len + tree[R(C)].len;
tree[C].numseg = tree[L(C)].numseg + tree[R(C)].numseg;
if(tree[R(C)].lbd && tree[L(C)].rbd) tree[C].numseg -= 2;
}
}
void make_tree(int s, int e, int C)
{
tree[C].left = s;
tree[C].right = e;
tree[C].mid = (s + e) >> 1;
tree[C].len = tree[C].cnt = tree[C].numseg = 0;
tree[C].lbd = tree[C].rbd = 0;
if(s == e) return;
make_tree(s, tree[C].mid, L(C));
make_tree(tree[C].mid + 1, e, R(C));
}
void update(int s, int e, int v, int C)
{
if(tree[C].left >= s && tree[C].right <= e)
{
tree[C].cnt += v;
up(C);
return;
}
if(tree[C].mid >= s) update(s, e, v, L(C));
if(tree[C].mid < e) update(s, e, v, R(C));
up(C);
}
int main()
{
int n;
scanf("%d", &n);
int low = 10000;
int high = -10000;
int m = 0;
for(int i = 0; i < n; i++)
{
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
low = min(low, a);
high = max(high, c);
seg[m++] = Seg(a, c, b, 1);
seg[m++] = Seg(a, c, d, -1);
}
sort(seg, seg + m);
int res = 0, last = 0;
make_tree(low, high, 1);
for(int i = 0; i < m; i++)
{
if(seg[i].l < seg[i].r) update(seg[i].l, seg[i].r - 1, seg[i].s, 1);
if(i < m - 1) res += tree[1].numseg * (seg[i + 1].h - seg[i].h);
res += abs(tree[1].len - last);
last = tree[1].len;
}
printf("%d\n", res);
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2002-Squares 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 1611 The Suspects 代码 并查集的应用
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1048,加强版的约瑟夫问题 难度中等
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
POJ2968代码有用,欢迎下载,POJ代码