文章目录
  1. 1. 线段交点
    1. 1.1. 快速排斥实验和跨立实验
    2. 1.2. 代码实现
    3. 1.3. POJ-2653

引言:喵老板又教了我一手。


线段交点

https://blog.csdn.net/Greepex/article/details/88190118

题目:

第三题,求线段交点,输入两组线段端点(整型),求其交点,不相交和无穷交点输出一句话就行,输出交点带小数的。
例如:
输入:
0 0 5 5
0 2 2 0
输出:
1 1

裸的计算几何。

快速排斥实验和跨立实验

https://www.cnblogs.com/dwdxdy/p/3230485.html

快速排斥和跨立实验。

假设有线段AB和CD,判断AB和CD是否有交点。

快速排斥:以AB为对角线,沿x和y轴方向作矩形是唯一的。以此法做出两条线段的对应的矩形。如果矩形有相交,则线段有相交的可能,否则没有。

跨立实验:记x为叉乘。ACxAD与BCxBD在z坐标上符号相反,且CAxCB与DAxDB在z坐标上符号相反,则通过跨立实验。形象解释就是说,A和B分布在CD两侧,C和D分布在AB两侧。

为什么要进行快速排斥实验?

举个例子,如果当AB和CD共线,此时ACxAD与BCxBD都为0,则无法判断是相交还是有无穷交点。

此时使用快速排斥可以判断。

那么如何在代码中实现快速排斥实验?

min(xA,xB)max(xC,xD)&&min(xC,xD)max(xA,xB)&&min(yA,yB)max(yC,yD)&&min(yC,yD)max(yA,yB)\begin {aligned} \min(x_A,x_B)&\leqslant \max(x_C,x_D)\&\&\\ \min(x_C,x_D)&\leqslant \max(x_A,x_B)\&\&\\ \min(y_A,y_B)&\leqslant \max(y_C,y_D)\&\&\\ \min(y_C,y_D)&\leqslant \max(y_A,y_B) \end {aligned}

代码实现

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct point{
double x,y;
};
point operator-(const point &y,const point &x){
point tmp=y;
tmp.x-=x.x;
tmp.y-=x.y;
return tmp;
}

bool rectCross(const point &a,const point &b,const point &c,const point &d){
return min(a.x,b.x)<=max(c.x,d.x)&&
min(c.x,d.x)<=max(a.x,b.x)&&
min(a.y,b.y)<=max(c.y,d.y)&&
min(c.y,d.y)<=max(a.y,b.y);
}
double xx(const point &a,const point &b){//向量a和b叉乘,返回新向量的y坐标
return a.x*b.y-b.x*a.y;
}
int z(double k){
if(fabs(k)<1e-8){
return 0;
}else if(k>0){
return 1;
}
return -1;
}
bool segmentCross(const point &a,const point &b,const point &c,const point &d){//引用一定要加上const,否则无法引用一个rvalue
//return xx(c-a,d-a)*xx(c-b,d-b)<0&&xx(a-c,b-c)*xx(a-d,b-d)<0;
return (z(xx(c-a,d-a))^z(xx(c-b,d-b)))<0&&(z(xx(a-c,b-c))^z(xx(a-d,b-d)))<0;//用异或防止爆int,但需要注意^的运算优先级很低,需要加括号。
}
point calc(const point &a,const point &b,const point &c,const point &d){
double kab=(b.y-a.y)/(b.x-a.x);
double kcd=(d.y-c.y)/(d.x-c.x);
point ret;
ret.y=(kcd*a.y-kab*c.y)/(kcd-kab);
ret.x=(ret.y-a.y)/kab;
return ret;
}
int main() {
point a,b,c,d;
int ax,ay,bx,by,cx,cy,dx,dy;
scanf("%d%d%d%d%d%d%d%d",&ax,&ay,&bx,&by,&cx,&cy,&dx,&dy);
a.x=ax;a.y=ay;
b.x=bx;b.y=by;
c.x=cx;c.y=cy;
d.x=dx;d.y=dy;
if(!xx(c-a,d-a)){//判共线
if(rectCross(a,b,c,d)){
puts("无穷交点");
}else{
puts("不相交");
}
}else{
if(!rectCross(a,b,c,d) && !segmentCross(a,b,c,d)){
puts("不相交");
}else{
point p=calc(a,b,c,d);
printf("%.2f %.2f\n",p.x,p.y);
}
}
return 0;
}

POJ-2653

练手:https://vjudge.net/problem/POJ-2653

Stan has n sticks of various length. He throws them one at a time on the floor in a random way. After finishing throwing, Stan tries to find the top sticks, that is these sticks such that there is no stick on top of them. Stan has noticed that the last thrown stick is always on top but he wants to know all the sticks that are on top. Stan sticks are very, very thin such that their thickness can be neglected.

Input

Input consists of a number of cases. The data for each case start with 1 <= n <= 100000, the number of sticks for this case. The following n lines contain four numbers each, these numbers are the planar coordinates of the endpoints of one stick. The sticks are listed in the order in which Stan has thrown them. You may assume that there are no more than 1000 top sticks. The input is ended by the case with n=0. This case should not be processed.

Output

For each input case, print one line of output listing the top sticks in the format given in the sample. The top sticks should be listed in order in which they were thrown.

The picture to the right below illustrates the first case from input.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct point{
double x,y;
};
struct segment{
point a, b;
bool below;
};
point operator-(const point &y,const point &x){
point tmp=y;
tmp.x-=x.x;
tmp.y-=x.y;
return tmp;
}
int xx(const point &a,const point &b){//向量a和b叉乘,返回新向量的z坐标
return a.x*b.y-b.x*a.y;
}
int z(double k){
if(fabs(k)<1e-8){
return 0;
}else if(k>0){
return 1;
}
return -1;
}
bool rectCross(const point &a,const point &b,const point &c,const point &d){
return min(a.x,b.x)<=max(c.x,d.x)&&
min(c.x,d.x)<=max(a.x,b.x)&&
min(a.y,b.y)<=max(c.y,d.y)&&
min(c.y,d.y)<=max(a.y,b.y);
}
bool segmentCross(const point &a,const point &b,const point &c,const point &d){//引用一定要加上const,否则无法引用一个rvalue
//return xx(c-a,d-a)*xx(c-b,d-b)<0&&xx(a-c,b-c)*xx(a-d,b-d)<0;
return (z(xx(c-a,d-a))^z(xx(c-b,d-b)))<0&&(z(xx(a-c,b-c))^z(xx(a-d,b-d)))<0;//用异或防止爆int,但需要注意^的运算优先级很低,需要加括号。
}
bool cross(const point &a,const point &b,const point &c,const point &d){
return rectCross(a,b,c,d)&&segmentCross(a,b,c,d);
}
vector<segment> vec;
int n;
int main() {
while(~scanf("%d",&n) && n){
vec.clear();
for(int i=0;i<n;i++){
point t,t2;
scanf("%lf%lf%lf%lf",&t.x,&t.y,&t2.x,&t2.y);
vec.push_back(segment{t,t2,false});
}
for(int i=0;i<vec.size();i++){
for(int j=i+1;j<vec.size();j++){
if(cross(vec[i].a,vec[i].b,vec[j].a,vec[j].b)){
vec[i].below=true;
break;
}
}
}
printf("Top sticks: ");
vector<int> vec2;
vec2.clear();
for(int i=0;i<vec.size();i++){
if(!vec[i].below){
vec2.push_back(i+1);
}
}
for(int i=0;i<vec2.size();i++){
if(i<vec2.size()-1){
printf("%d, ",vec2[i]);
}else{
printf("%d.\n",vec2[i]);
}
}
}
return 0;
}

贴个邝斌学长的:

https://www.cnblogs.com/kuangbin/p/3189750.html

文章目录
  1. 1. 线段交点
    1. 1.1. 快速排斥实验和跨立实验
    2. 1.2. 代码实现
    3. 1.3. POJ-2653