【37%】【poj1436】Horizontally Visible Segments
Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 5200 | Accepted: 1903 |
Description
segments are said to form a triangle of segments if each two of them are horizontally visible. How many triangles can be found in a given set of vertical segments?
Task
Write a program which for each data set:
reads the description of a set of vertical segments,
computes the number of triangles in this set,
writes the result.
Input
The first line of each data set contains exactly one integer n, 1 <= n <= 8 000, equal to the number of vertical line segments.
Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:
yi', yi'', xi - y-coordinate of the beginning of a segment, y-coordinate of its end and its x-coordinate, respectively. The coordinates satisfy 0 <= yi' < yi'' <= 8 000, 0 <= xi <= 8 000. The segments are disjoint.
Output
Sample Input
1
5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
Sample Output
1
Source
【题解】
这题的意思是在一个平面里面给你n条线段,是竖直的,然后给你它的横坐标x和竖直方向上的两个端点坐标y1,y2;
然后“可见”的意思是,在这个平面里面放一段水平线段。然后问是否有两条输入的竖直线段被这条水平线段经过。如果有的话还需要这条水平线在这两条线段中间没有穿过其他的输入的竖直线。如果满足上述条件。则称这两条线段可见。只要有任意一条水平线(最少一条)满足就称它们为可见的。
题目说的triangle的意思就是说要找到3条这样两两可见的线段。
问这样的triangle有多少个。
思路:
先按照x轴升序排序那些输入的竖直线段。我这里在排序前记录了它原来的编号。但是我觉得完全可以在排序完之后再记录它们的编号。因为最后只要求数目不要求输出方案;
然后就把这个问题看做是平面上的线段,即从右往左在竖直面上不断地覆盖线段。
覆盖一条线段x的时候,就看一下,当前的竖直面上有哪些之前线段会被覆盖到。如果被覆盖到那说明什么???当然就是它们俩是可见的!
所以我们用一个bo[MAXN][MAXN]来记录某两个编号的线段是否可见。
在做线段树的时候顺便记录就可以了。
然后就是最后的统计数目;
这样
for (int i = 1;i <= n;i++)
for (int j = i+1;j <= n;j++)
if (bo[i][j])
for (int k = i+1;k <= j-1;k++)
if (bo[i][k] && bo[k][j])
ans++;
很容易理解的吧
最后还要提一个问题。
就是类似这样的数据
1 4 0
1 2 1
3 4 1
1 4 2
就是当我们前3个都覆盖了,第4个再覆盖上去编号为4的和编号为1的是否是可见的呢??
显然应该是可见的才对。
因为y坐标的2到3是没有被编号2和编号3线段覆盖的。
但是如果我们正常地按线段树去做会得出1和4是不可见的错解,所以需要把y坐标的对应值都乘上2;
2 8 0
2 4 1
6 8 1
2 8 2
这样线段树就能够判断出[4,6]这个区间是编号1的了。然后4和1就会被判断为可见了。
【代码】
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> const int MAXN = 8000+10; using namespace std; struct bian //记录线段的信息。
{
int x, y1, y2,bianhao;
}; bian a[MAXN];
int n,color[MAXN*2*4];//color相当于线段树中的lazy_tag现在被用来记录线段的颜色
__int64 ans;//记录答案
bool bo[MAXN][MAXN];//判断任意两条线段是否可见。 void input_data()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d", &a[i].y1, &a[i].y2, &a[i].x);
a[i].y1 = a[i].y1*2;a[i].y2 = a[i].y2*2;//为防止错节要乘2
if (a[i].y1 > a[i].y2)
{
int t = a[i].y1;
a[i].y1 = a[i].y2;
a[i].y2 = t;
}
a[i].bianhao = i;
}
} int cmp(const bian &a, const bian &b)
{
if (a.x < b.x)
return 1;
return 0;
} void deal_withlazy(int rt)//处理懒惰标记
{
if (color[rt] != 0)
{
color[rt << 1] = color[rt << 1 | 1] = color[rt];//直接往下传递就可以了。
color[rt] = 0;
}
} void query(int l, int r, int now, int begin, int end, int rt)
{//当前节点的编号为rt,它的区间范围是begin,end;
if (color[rt] != 0)//因为l,r肯定是和begin和end有交集的
{//如果begin和end全部被覆盖成了某种颜色
bo[now][color[rt]] = true;//则这种颜色肯定要被覆盖最少一部分了 则记录它们可见。
bo[color[rt]][now] = true;
return;
}
if (begin >= end)
return;
deal_withlazy(rt);//这句可以省略掉
int m = (begin + end) >> 1;
if (l <= m)
query(l, r, now, begin,m,rt<<1);
if (m < r)
query(l, r, now, m+1,end,rt<<1|1);
} void updata(int l, int r, int now, int begin, int end, int rt)
{
if (l <= begin && end <= r) //如果完全在需要覆盖的里面就直接覆盖颜色
{
color[rt] = now;
return;
}
int m = (begin + end) >> 1;
if (begin >= end)
return;
deal_withlazy(rt);//这句就不能省了,因为要对下面进行操作了。
if (l <= m)
updata(l, r, now, begin,m,rt<<1);
if (m < r)
updata(l, r, now, m+1,end,rt<<1|1);
} void get_ans()
{
for (int i = 1; i <= n; i++)
{
query(a[i].y1, a[i].y2, a[i].bianhao, 0, 16000,1);
updata(a[i].y1, a[i].y2, a[i].bianhao, 0, 16000, 1);
}
for (int i = 1; i <= n - 1; i++)
for (int j = i + 1; j <= n; j++)//求解
if (bo[i][j])
for (int k = i + 1; k <= j - 1; k++)
if (bo[k][i] && bo[k][j])
ans++;
} void init() //每次的初始化。
{
memset(bo, false, sizeof(bo));
memset(color, 0, sizeof(color));
ans = 0;
} void output_ans()
{
cout << ans << endl;
} int main()
{
//freopen("F:\\rush.txt", "r", stdin);
//freopen("F:\\rush_out.txt", "w", stdout);
int t;
scanf("%d", &t);
while (t--)
{
init();
input_data();
sort(a + 1, a + 1 + n, cmp);
get_ans();
output_ans();
}
return 0;
}
最新文章
- mysql 性能配置优化
- 揭秘Facebook首个数据中心:全球15亿用户的账户信息都在这里
- 关于在for循环中绑定事件打印变量i是最后一次。
- Android中的Intent Filter匹配规则介绍
- goquery
- jsp请求由servlet响应的方式
- RPi 2B python opencv camera demo example
- Openjudge-计算概论(A)-统计字符数
- iOS8学习笔记2--autolayout
- 关于linux上postgresql的一些理解
- [Swift]LeetCode150. 逆波兰表达式求值 | Evaluate Reverse Polish Notation
- 图书馆管理系统(C语言)
- angular select2 ng-model 取值 ng-change调用方法
- EF数据迁移
- Python3之max key参数学习记录
- Java Script正则表达式语法学习
- sshd服务防止暴力破解
- cat /proc/net/sockstat
- pycharm 远程开发
- Unity中的Transform Gizmo中的Pivot和Center
热门文章
- 趣闻|Python之禅(The Zen of Python)
- COGS 163 [USACO Mat07] 牛语
- COGS——T 1786. 韩信点兵
- [React &; Testing] Snapshot testings
- php图像处理(thinkphp框架有相对强大的图像处理功能)
- Express框架是什么
- 一种较为隐蔽ConcurrentModificationException情形
- 1.IntelliJ IDEA搭建SpringBoot的小Demo
- 洛谷 P3131 [USACO16JAN]子共七Subsequences Summing to Sevens
- nginx源代码分析--事件模块 &;amp; 琐碎