Horizontally Visible Segments
Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 3805 | Accepted: 1392 |
Description
There is a number of disjoint vertical line segments in the plane. We say that two segments are horizontally visible if they can be connected by a horizontal line segment that does not have any common points with other vertical segments. Three different vertical 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.
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 the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 20. The data sets follow.
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.
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
The output should consist of exactly d lines, one line for each data set. Line i should contain exactly one integer equal to the number of triangles in the i-th data set.
Sample Input
1 5 0 4 4 0 3 1 3 4 2 0 2 2 0 2 3
Sample Output
1
题意:
给出 T,代表有 T 组样例。每个样例给出一个 n(1 ~ 8000),代表有 n 条垂直的线,后给出这 n 条垂直线的 y1,y2,x (0 ~ 8000)值,寻找任意的三条线,两两之间用横线穿过当且仅当穿过这两条垂直线,寻找有多少个组合满足这样条件的三条线。
思路:
线段树 + 区间覆盖。不需要离散化,但是存在一个问题就是,有可能两条线用一条水平线穿过只穿过了两条线的端点,而线段树维护子节点是维护一个线段元的覆盖情况的,所以要对 y 坐标方法处理,即 X 2。这样的话就可以转化成线段元来处理了。每添加一条线前先查询该区间能到达的线分别是哪些,再插入进去,用 Map 标记每条线的到达情况,后暴力求解 Map [ i ] [ j ] == 1 且 Map [ i ] [ k ] 且 Map [ j ] [ k ] 的一共有多少即可。记得建树和查询的时候也要对树 X 2 来建和查询,不够细心 WA 了几次。数据比较小,也不需要离散化。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX = 8005; typedef struct { int x, y1, y2; } node; node line[MAX]; bool Map[MAX][MAX]; int cover[MAX * 5]; int n; bool cmp (node a, node b) { return a.x < b.x; } void push_down (int node) { if (cover[node]) { cover[node << 1] = cover[node]; cover[node << 1 | 1] = cover[node]; cover[node] = 0; } } void build (int node, int l, int r) { if (r == l) { cover[node] = 0; } else { int mid = (r + l) >> 1; build(node << 1, l, mid); build(node << 1 | 1, mid + 1, r); cover[node] = 0; } } void updata (int node, int l, int r, int cl, int cr, int c) { if (cl > r || cr < l) return; if (cl <= l && cr >= r) { cover[node] = c; return; } if (r == l) return; push_down(node); int mid = (r + l) >> 1; if (cl <= mid) updata(node << 1, l, mid, cl, cr, c); if (cr >= mid) updata(node << 1 | 1, mid + 1, r, cl, cr, c); } void query (int node, int l, int r, int ql, int qr, int q) { if (ql > r || qr < l) return; if (ql <= l && qr >= r) { if (cover[node]) { Map[q][ cover[node] ] = 1; return; } } if (r == l) return; push_down(node); int mid = (r + l) >> 1; if (ql <= mid) query(node << 1, l, mid, ql, qr, q); if (qr >= mid) query(node << 1 | 1, mid + 1, r, ql, qr, q); } void solve () { int sum = 0; for (int i = n; i >= 3; --i) { for (int j = i - 1; j >= 2; --j) { if (Map[i][j]) { for (int k = j - 1; k >= 1; --k) { if (Map[i][k] && Map[j][k]) ++sum; } } } } printf("%d\n", sum); } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); memset(Map, 0, sizeof(Map)); build(1, 0, MAX * 2); for (int i = 1; i <= n; ++i) { scanf("%d%d%d", &line[i].y1, &line[i].y2, &line[i].x); } sort(line + 1, line + 1 + n, cmp); for (int i = 1; i <= n; ++i) { query(1, 0, MAX * 2, line[i].y1 * 2, line[i].y2 * 2, i); updata(1, 0, MAX * 2, line[i].y1 * 2, line[i].y2 * 2, i); } solve(); } return 0; }
相关推荐
藏经阁-Horizontally Scalable Relation
藏经阁-Horizontally Scalable Relational Databases with Spark.pdf
水稻基因组中通过BLAST同源搜索和系统发育树预测的2878条水平转移基因,郭兴益,王煜,水平基因转移(HGT)现象在许多原核生物中均有报导,对于其适应新的生境有重要意义。有关原核生物DNA转移到高等真核生物核基因...
Dolly.js-轻松克隆表 Dolly.js是一个简单而... console.log(this, "has been cloned " + ui.cloneX + " cells horizontally and " + ui.cloneY + " vertically."); } }); 您可以在examples目录中找到更详细的examples
In this work, we propose a novel packaging scheme with horizontally layered QDs-phosphor nanocomposites to obtain an enhanced optical and thermal performance for WLEDs. Three different WLEDs, ...
描述:使用Shader将图片进行水平/竖直镜像翻转 资源类型:unitypackage,导入即可使用 ...It is possible to autonomously mirror and flip graphics horizontally or vertically during runtime, as well as simultane
Grid can scroll data smoothly vertically and horizontally. + Hot track. Grid can highlight a cell or a row under mouse cursor. + Grid can show vertical line in gradient mode between data rows and...
- flip the image horizontally or vertically - rotate the image +/- 90d ## Guide - Please run `npm install` in the folder to install npm modules. - Visit the static ...
如何使用 // git clone npm i 启动Redis服务器使用您的Redis服务器的信息填写nodemon.json中缺少的环境变量 npm start 大量的console.logs ......... 此仓库模拟2个Web客户端和2个节点服务器 客户端1连接到服务器1...
11.Added: the 'Arrange child windows on running queries' option: Tile vertically/horizontally and Cascade 12.Added: an option to scan titles only within the 'Search by RegExp' plugin. 13.Improved: ...
Page position+1 will be visible if * positionOffset is nonzero. * @param positionOffset * Value from [0, 1) indicating the offset from the page at * position. * @param ...
AC Justify Center HSel - Center-justify horizontally AC Justify Right Sel - Right-justify AC Justify Block HSel - Block-justify horizontally AC Justify Top Sel - Left-justify AC Justify Center VSel - ...
I have coded an entire chat application using the Spring Framework, WebSocket, Cassandra, Redis, RabbitMQ, and MySQL, and I discuss how you can horizontally scale this application implementing a ...
The QBoxLayout class lines up widgets horizontally or vertically. QHBoxLayout and QVBoxLayout are convenience subclasses of QBoxLayout. QGridLayout lays out widgets in cells by dividing the available ...
on android ImageView when it's being vertically or horizontally scrolled (moving) on the screen. I wrote an article explaining how this works and implemented, please check it out ...
开源项目-celrenheit-sandglass.zip,Sandglass is a distributed, horizontally scalable, persistent, time sorted message queue
Lay Out Horizontally : 纵向布局 Lay Out Vertically:横向布局 Lay Out Horizontally in Splitter: 纵向分裂式布局 Lay Out Vertically in Splitter:横向分裂式布局 Lay Out in a Grid: 网格布局 Lay Out in a ...
After this, you'll learn how to set up replication, use load balancing to scale horizontally, and troubleshoot errors. Finally, you will get acquainted with useful tools available in the PostgreSQL ...
In the family of bridge systems the cable supported bridges are ...(4)the anchor blocks (or anchor piers) supporting the cable system vertically and horizontally, or only vertically, at the extreme ends.