| Life is a Line |
| Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) |
| Total Submission(s): 217 Accepted Submission(s): 81 |
| |
Problem DescriptionThere is a saying: Life is like a line, some people are your parallel lines, while others are destined to meet you.
Maybe have met, maybe just a matter of time, two unparallel lines will always meet in some places, and now a lot of life (i.e. line) are in the same coordinate system, in a given open interval, how many pairs can meet each other?
|
InputThere are several test cases in the input.
Each test case begin with one integer N (1 ≤ N ≤ 50000), indicating the number of different lines.
Then two floating numbers L, R follow (-10000.00 ≤ L Then N lines follow, each line contains four floating numbers x1, y1, x2, y2 (-10000.00 ≤ x1, y1, x2, y2 ≤ 10000.00), indicating two different points on the line. You can assume no two lines are the same one.
The input terminates by end of file marker.
|
OutputFor each test case, output one integer, indicating pairs of intersected lines in the open interval, i.e. their intersection point’s x-axis is in (l, r).
|
Sample Input3
0.0 1.0
0.0 0.0 1.0 1.0
0.0 2.0 1.0 2.0
0.0 2.5 2.5 0.0 |
Sample Output1 问题：求在 （l, r）范围内有多少个交点，看起来好像是个几何题。。。时间上是一个求逆序数的问题。
只要直线不平行于y轴就一定会 跟 x = l, x = r这两条直线相交。对于任意两条直线x=l,和x=r的交点分别为xl,xr，两直线在(L,R)相交，必然有 所以可以用逆序数来求解。
-
-
-
-
-
-
-
-
- （这一段转的别人的）
#include
#include
#include
#include
using namespace std;
const int maxn = 50000;
struct Line{
double a, b;
int num;
}line[50050];
int tree[50500];
int lowbit(int x) {
return x & (-x);
}
void add(int pos) {
for (int i = pos; i <= maxn; i += lowbit(i)) {
tree[i]++;
}
}
int sum(int pos) {
int ans = 0;
for (int i = pos; i >= 1; i -= lowbit(i)) {
ans += tree[i];
}
return ans;
}
int main() {
int n;
double left, right;
double x1, x2, y1, y2;
while (cin >> n) {
int parallel_y = 0;
int unparallel = 0;
scanf("%lf%lf", &left, &right);
for (int i = 0; i scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
if (x1 == x2) {
if (x1 > left && x1 parallel_y++;
}
} else {
double k = (y1 - y2) / (x1 - x2);
double b = y1 - k * x1;
line[unparallel].a = left * k + b;
line[unparallel++].b = right * k + b;
}
}
sort(line, line + unparallel, [](Line l1, Line l2)->bool{return l1.a == l2.a ? l1.b for (int i = 0; i line[i].num = i + 1;
}
sort(line, line + unparallel, [](Line l1, Line l2)->bool{return l1.b == l2.b ? l1.a > l2.a : l1.b > l2.b;});
memset(tree, 0, sizeof(tree));
int ans = 0;
for (int i = 0; i add(line[i].num);
ans += sum(line[i].num - 1);
}
cout < }
}
|
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号