OI-计算几何基础
OI-计算几何初步
1.前置知识点
pi = acos(-1);
cos(π) = -1;
c ^ 2 = a^2 + b^2 + 2*a*b*cos(ß); //余弦定理 2.浮点数比较
const double eps = 1e-8;
int sign(double x) //符号函数
{
if (fabs(x) < eps) return 0;
if (x < 0) return -1;
}
int cmp(double x,double y){
if (fabs(x - y) < eps) return 0;
return (x-y) ? -1:1;
}
3.向量
点与向量
typedef struct
{
int x;
int y;
} Point;
typedef Point Vector; //(0,0)到(x,y)的向量向量的加减法和线性组合
如图，
\vec{AB}+\vec{BC} = \vec{AC} \vec{a} + \vec{b} = \vec{c} \vec{a} = ( x_1,y_1 ) , \vec{b} = (x_2,y_2), \vec{c} = (x_1+x_2,y_1+y_2)
如图
\vec{AB} = (2,2)
数乘向量 k*\vec{a} = k\vec{a}
向量的内积（点积）
- 几何意义
已知向量
- 定义
- 代码
double dot( Point a, Point b )
{
return a.x * b.x + a.y * b.y ;
}向量的外积
-
几何意义:
向量A 与B 张成的平行四边形的有向面积，B 在A 的顺时针方向时为正 -
定义
- 代码
double cross(Point a,Point b)
{
return a.x * b.y - b.x * a.y;
}常用函数
//向量取模
double get_length(Point a)
{
return sqrt(dot(a,b));
}
//计算向量夹角
double get_angle(Point a,Point b)
{
return acos(dot(A,B) / get_length(a) / get_length(b));
}
//计算两个向量构成的平行四边形的有向面积
double area(Point a,Point b,Point c){
return cross(b - a,c - a);
}
//向量A顺时针旋转C的角度
double rotate(Point a,double angle ){
return Point(a.x * cos(angle) + a.y * sin(angle) , -a.x * sin(angle) + a.y * cos(angle));
}4.点与线
4.1 直线定理
(1) 一般式
ax + by + c = 0 (2) 点向式
p0 + vt (3) 斜截式
y = kx + b 4.2 常用操作
判断点在直线上
A * B = 0 //两直线相交 Point get_line_intersection(Point p,Vector v,Point q,Vector w) { Vector u = p - q; double t = cross(w,u) / cross(v,w); return p + v * t; } //点到直线的距离 double distance_to_line(Point p,Point a,Point b) { Vector v1 = b - a,v2 = p - a; return fabs(cross(v1,v2) / get_length(v1)); } //点到线段的距离 double distance_to_segment(Point p,Point a,Point b) { if ( a == b ) return get_length(p-a); Vector v1 = b - a,v2 = p - a,v3 = p - b; if ( sign(dot(v1,v2)) < 0 ) return get_length(v2); if ( sign(dot(v1,v3)) < 0 ) return get_length(v3); return distance_to_line(p,a,b); } //点在直线上的投影 double get_line_projection(Point p,Point a,Point b) { Vector v = b - a; return a + v ( dot(v,p - a) / dot(v,v)); } // 点是否在线段上 bool is_on_segment(Point p,Point a,Point b) { return sign(cross(p - a,p - b)) == 0 && sign(dot(p - a,p - b)) <= 0; } // 判断两线段是否相交 bool is_segment_intersection(Point a1,Point a2,Point b1,Point b2) { double c1 = cross(a2 - a1,b1 - a1) ,c2 = cross(a2 - a1.b2 - b1); double c3 = cross(b2 - b1,a2 - b1) ,c4 = cross(b2 - b1,a1 - b1); return sign(c1) * sign(c2) <= 0 && sign(c3) * sign(c4) <= 0; }
5. 多边形
5.1 三角形
三角形的面积
(1) 向量叉乘
(2) 海伦公式
p = \frac{a+b+c}{2}
S = \sqrt{p(p-a)(p-b)(p-c)} 三角形的四心
5.2 普通多边形
通常按逆时针存储所有点
5.2.1 定义
(1) 多边形 又在同一平面且不在同一直线上的多条线段首位顺次连接且不相交所组成的图形叫多边形
(2) 简单多边形
(3) 凸多边形
5.2.2常用函数
//求多边形面积 double polygon_area(Point p[],int n) { double s = 0; for (int i = 1 ; i + 1 < n ; i ++ ) s += cross(p[i] - p[0],p[i + 1] - p[i]); return s/2; }判断点是否在多边形里
a.射线法，从该点任意做一条和所有边都不平行的射线，交点个数为偶数，则在多边形外，为奇数，则在多边形里
b.转角法
判断点是否在凸多边形内 只需判断点是否在所有边的左边
5.3 皮克定理其中 a 表示多边形内部的点数， b 表示多边形边界上的点数，S 表示多边形的面积
6.圆
圆与直线交点
两圆交点
点到圆的切线
两圆公切线
两圆相交面积
Aw 2981.玩具
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long LL;
typedef pair<LL,LL> PLL;
const int N = 1e4 + 10;
int n,m,ans[N];
PLL a[N],b[N];
LL cross( LL x1,LL y1,LL x2,LL y2)
{
return x1 * y2 - x2 * y1;
}
LL area(PLL a,PLL b,PLL c)
{
return cross(b.x - a.x,b.y - a.y,c.x - a.x,c.y - a.y);
}
int find(LL x,LL y)
{
int l = 0,r = n;
while( l < r )
{
int mid = l + r >> 1;
if ( area(b[mid],a[mid],{x,y}) > 0 ) r = mid;
else l = mid + 1;
}
return r;
}
signed int main(){
bool is_first = true;
while ( scanf("%d",&n ),n)
{
LL x1,y1,x2,y2;
scanf("%d%lld%lld%lld%lld",&m,&x1,&y1,&x2,&y2);
for (int i = 0 ; i < n ; i ++ )
{
LL u,l;
scanf("%lld%lld",&u,&l);
a[i] = {u,y1},b[i] = {l,y2};
}
a[n] = {x1,y1},b[n] = {x2,y2};
memset(ans,0,sizeof ans);
if ( is_first ) is_first = false;
else puts("");
while(m--)
{
LL x,y;
scanf("%lld%lld",&x,&y);
ans[find(x,y)] += 1;
}
for (int i = 0 ; i <= n ; i ++ )
printf("%d: %d\n",i,ans[i]);
}
}
//二分+叉乘判断点是否在向量的左边Aw 2984.线段
/*
#define Withers AKIOI
#define ~syLph~ AK GENERALS.IO
#define OrangeGong AK WOT
#define -(Anonymous)- AK WOW
#define DancingLinks AK NOI
#define 23154 AKIOI 0613
枚举线段的两个端点，如果有一条直线穿过所有的线段，则通过两次旋转就一定能得到合法的直线
然后就是判断直线与所有线段是否有交点
T组数据,枚举两个点O(n^2),依次与每条线段比较O(n)
总时间复杂度O(T*n^3)，2s的话应该能过
*/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef pair<double,double> PDD;
const int N = 210;
const double eps = 1e-8;
int n;
PDD q[N],a[N],b[N];
int sign(double x)
{
if ( fabs(x) < eps ) return 0;
if ( x < 0 ) return -1;
else return 1;
}
int cmp(double x,double y)
{
if ( fabs(x-y) < eps ) return 0;
if ( x < y ) return -1;
return 1;
}
double cross(double x1,double y1,double x2,double y2)
{
return x1 * y2 - x2 * y1;
}
double area( PDD a,PDD b,PDD c )
{
return cross(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
}
bool check()
{
for (int i = 0 ; i < n * 2 ; i ++ )
{
for (int j = i + 1 ; j < n * 2 ; j ++ )
{
if ( !cmp(q[i].x,q[j].x) && !cmp(q[i].y,q[j].y) ) continue;
bool flag = true;
for (int k = 0 ; k < n ; k ++ )
{
if ( sign(area(q[i],q[j],a[k])) * sign(area(q[i],q[j],b[k])) > 0)
{
flag = false;
break;
}
}
if ( flag ) return true;
}
}
return false;
}
signed int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for (int i = 0 , k = 0 ; i < n ; i ++ )
{
double x1,y1,x2,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
q[k++] = {x1,y1},q[k++] = {x2,y2};
a[i] = {x1,y1} , b[i] = {x2,y2};
}
if (check()) puts("Yes!");
else puts("No!");
}
return 0;
}完结撒花????