两直线交点
首先我们知道两点能够确定一条直线，能够得到直线的方程
假设现在有两条直线
联立两个方程就可以得到一个简答的答案
实际上就是联立了方程组
利用线性代数的解法转换为行列式就是
解出的i,j,k对应x,y,d;
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
struct Point{
double x,y;
};
struct line
{
double a,b,c;
};
line getline(Point p1,Point p2)
{
return line{1/(p2.x-p1.x),-1/(p2.y-p1.y),(p1.y/(p2.y-p1.y)-p1.x/(p2.x-p1.x))};
}
Point solve(line l1,line l2)
{
double D = l1.a*l2.b-l2.a*l1.b;
if(D==0)return Point{1e18,1e18};
return Point{l1.b*l2.c-l2.b*l1.c/D,l2.a*l1.c-l1.a*l2.c/D};
}
int main()
{
solve(l1,l2);
}
|
求任意多边形的面积
叉乘
假设向量$\vec{a}=(x_1,y_1),\vec{b}=(x_2,y_2)$
那么向量的叉乘定义为
结果也就是两个向量构成三角形面积的两倍，使用这个方法开求多边形的面积
,假设多边形的点为$p_1,p_2\cdots,p_n;v_i为辅助点O与p_i的向量$。
圆与直线的关系
直线与圆的交点
相离，相交，相切，可以通过圆心与直线的距离和半径的大小比较来判断
圆与圆的交点
通过圆心得距离与两个圆得半径和来判断圆与圆之间的关系，有外离，内含，相交，相切
外离
当$r1+r2<d$时，两个圆无交点，为外离
内含
当$r1>d||r2>d$时为内含
相切
当$r1+r2==d$时，为相切，相切的情况下，就可以转化为直线与圆的关系求出切点。
相交
当$r1+r2<d$时，相交，相交求交点的做法联立两个方程带入即可
极角排序
叉积排序，atan2排序与象限排序
叉积排序速度慢，精度高，但是可能会炸范围，atan2精度低，单是速度块。
叉积排序
选定基准点$O(x，y)$
1
2
3
4
5
6
7
8
| double Cross(Point p1,Cross p2)
{
return p1.x*p2.y-p2.x-p1.y;
}
bool cmp(Point p1,Point p2){
if(Cross(p1,p2)==0)return p1.x<p2.x;若极角相同返回x小的
reutrn Cross(p1,p2)>0;
}
|
atan2排序
1
2
3
4
5
6
| atan2(double y,double x);
bool com(Point p1,Point p2)
{
if(atan2(p1.y,p1.x)-atan2(p2.y,p2.x)!=0)return atan2(p1.y,p1.x)<atan2(p2.y,p2.x);
else return p1.x<p2.x;
}
|
象限排序
1
2
3
4
5
6
7
8
9
10
11
12
|
int Quadrant(Point A){
if(A.x>0&&A.y>=0)return 1;
if(A.x<=0&&A.y>0)return 2;
if(A.x<0&&A.y<=0)return 3;
if(A.x>=0&&A.y<0)return 4;
}
bool cmp2(Point A,Point B){
if(Quadrant(A)==Quadrant(B))
return cmp1(A,B);
else return Quadrant(A)<Quadrant(B);
}
|
例题
Poj1696
代码实现
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
| #include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 1e5+10;
#define eps
struct Point{
double x,y;
int id;
}Pole,p[N];
struct Vector{
double x,y;
};
int syn(double x)
{
if(fabs(x)<1e-8)return 0;
else if(x>0)return 1;
return -1;
}
double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
Vector operator - (Point a,Point b){return {a.x-b.x,a.y-b.y};}
bool cmp(Point a,Point b)
{
if(syn(Cross(a-Pole,b-Pole))==0)return a.x<b.x;
return Cross(a-Pole,b-Pole)>0;
}
int n;
void solve()
{
scanf("%d",&n);
int index = 1;
for(int i=1;i<=n;i++)
{
scanf("%d%lf%lf",&p[i].id,&p[i].x,&p[i].y);
if(i!=1&&p[index].y>p[i].y)index=i;
else if(i!=1&&p[index].y==p[i].y&&p[i].x<p[index].x)index=i;
}
swap(p[1],p[index]);
Pole = p[1];
for(int i=2;i<=n;i++)
{
sort(p+i,p+1+n,cmp);
Pole=p[i];
}
printf("%d",n);
for(int i=1;i<=n;i++)
{
printf(" %d",p[i].id);
}
printf("\n");
}
int main()
{
int t;
scanf("%d",&t);
while(t--)solve();
}
|