计算几何

如何证明一个四边形是凹四边形

题目描述

如何证明一个四边形是凹四边形

算法1

用AC在直线BD的一侧来证明是凹四边形

C++ 代码

const int N=2e5+10;
int n,m,k,a[N],b[N];
int x[N],y[N];
int val(int i,int j,int k){
	return (y[j]-y[k])*(x[i]-x[k])+(y[k]-y[i])*(x[j]-x[k]);
}
void solve(){
	//try it again.
	up(1,4)cin>>x[o]>>y[o];
	if(val(1,2,4)*val(3,2,4)>0)NO
	if(val(2,1,3)*val(4,1,3)>0)NO
	YES
}

算法2

(用BC在直线AD的两侧来证明是凹四边形

C++ 代码

const int N=2e5+10;
int n,m,k,a[N],b[N];
int x[N],y[N];
int val(int i,int j,int k){
	return (y[j]-y[k])*(x[i]-x[k])+(y[k]-y[i])*(x[j]-x[k]);
}
void solve(){
	//try it again.
	up(1,4)cin>>x[o]>>y[o];
	if(val(1,2,3)*val(4,2,3)<0)NO
	if(val(2,1,4)*val(3,1,4)<0)NO
	YES
}

E 鸡算几何 (计算几何)

链接：E-鸡算几何_2023牛客寒假算法基础集训营1 (nowcoder.com)

in

4
0 1 0 0 1 0
1.000000000 0.000000000 0.000000000 0.000000000 0.000000000 1.000000000
1 0 0 0 0 2
2.000000000 0.000000000 0.000000000 0.000000000 0.000000000 1.000000000
45 67 0 0 26 -24
3.021000000 47.390000000 -41.979000000 -19.610000000 -74.030581210 -4.620132023
50 -58 0 0 65 88
75.106000000 -9.735000000 25.106000000 48.265000000 -71.510643929 -3.059693042

out

NO
YES
YES
YES

说明

具体来说，二维平面上有一根(L)型的铁丝，由AB和BC两条线段组成，鸡可以用以下三种操作玩铁丝：

1、在平面内任意地平移铁丝，即铁丝上每一个点横坐标都变化(Delta x)、纵坐标都变化(Delta y)；

2、以B点为轴，任意地旋转铁丝，旋转是在平面上进行的（即旋转过程中铁丝不能离开地面）；

3、鸡是三维生物！鸡将该铁丝拿起，在自己手里任意的调整铁丝的姿态后（鸡不能使铁丝发生形变）再随意放回平面上任意位置。

鸡可以任意（任意顺序、任意次数、不同的操作可以交替使用）使用上述三种操作来操作铁丝，经过一段时间的操作后，得到新铁丝的位置可以用线段DE和EF描述。注意DE并不保证与AB对应，EF同理，即DEF只描述操作后铁丝的形状。

现在，你想知道只根据ABC与DEF的信息，是否可以断言鸡一定使用过至少一次第三种操作。

可以看出，操作3能做到而操作1+2做不到的，就是将铁丝进行沿AB或

BC的翻转（例如A变为关于BC的对称点），这可以使用叉乘来判断；

具体来说，首先将AB、BC和ED、EF按照长度进行匹配，找到ABC与DEF

的关系，假设ABC与DEF一一对应，则cross(AB,BC)与cross(DE,EF)

正负性不同时，说明一定进行了操作3，cross为叉乘；

特别的，AB和BC长度相等时无法判断，总是no；

若遇到精度问题，考虑比较AB和BC长度时使用整数而非浮点数比较；

或在ABC和DEF进行匹配时使用较大的eps（如1e-5，注意这里使用较

小的如1e-9等eps反而可能炸）

这道题用到了叉乘的板子，在下面贴一下

T cross(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
}

这个嘛就是叉乘的板子hhh

将叉乘和这个题结合讲一下

key code

using T = double;
struct Point {
    T x;
    T y;
    Point(T x = 0, T y = 0) : x(x), y(y) {}
      
    Point &operator+=(const Point &p) {
        x += p.x, y += p.y;
        return *this;
    }
    Point &operator-=(const Point &p) {
        x -= p.x, y -= p.y;
        return *this;
    }
    Point &operator*=(const T &v) {
        x *= v, y *= v;
        return *this;
    }
    friend Point operator-(const Point &p) {
        return Point(-p.x, -p.y);
    }
    friend Point operator+(Point lhs, const Point &rhs) {
        return lhs += rhs;
    }
    friend Point operator-(Point lhs, const Point &rhs) {
        return lhs -= rhs;
    }
    friend Point operator*(Point lhs, const T &rhs) {
        return lhs *= rhs;
    }
};
  
T dot(const Point &a, const Point &b) {
    return a.x * b.x + a.y * b.y;
}
  
T cross(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
}
 
const int N=2e5+10;
void solve(){
    //try it again.
    Point a[6];
    up(0,5)cin>>a[o].x>>a[o].y;
    if(cross(a[0]-a[1],a[2]-a[1])<0)swap(a[0],a[2]);
    if(cross(a[3]-a[4],a[5]-a[4])<0)swap(a[3],a[5]);
    db len0=sqrt(dot(a[0]-a[1],a[0]-a[1]));
    db len1=sqrt(dot(a[3]-a[4],a[3]-a[4]));
    if(abs(len0-len1)>1e-9)YES
    NO
}

E-公平守望的灯塔

E-公平守望的灯塔_2023牛客寒假算法基础集训营3 (nowcoder.com)

小红在平面直角坐标系上选择了两个点(A)和(B)（保证两点不重合），它们的坐标分别为((x_A,y_A))和((x_B,y_B))。小红希望你选择一个整点(C)，满足三角形(ABC)为以(AB)为斜边的等腰直角三角形。你能帮帮她吗？
整点的定义：横坐标和纵坐标均为整数。

输入描述:

四个整数(x_A,y_A,x_B,y_B)，用空格隔开。
$ -10^9leq x_A,y_A,x_B,y_B leq 10^9$

输出描述

如果无解，请直接输出"No Answer!"
否则输出两个整数(x_C,y_C)，代表(C)点的坐标。有多解时输出任意即可。

in

1 0 0 1

out

0 0

这个题可以套用一下板子

先求出对应的两个点，再看这两个点满不满足题意

因为我们知道double 的答案应该怎么求

然后再强转成int型

如果强转以后仍然满足条件

那么就是成立的

key code

using T = long long;
struct Point {
    T x;
    T y;
    Point(T x = 0, T y = 0) : x(x), y(y) {}
     
    Point &operator+=(const Point &p) {
        x += p.x, y += p.y;
        return *this;
    }
    Point &operator-=(const Point &p) {
        x -= p.x, y -= p.y;
        return *this;
    }
    Point &operator*=(const T &v) {
        x *= v, y *= v;
        return *this;
    }
    friend Point operator-(const Point &p) {
        return Point(-p.x, -p.y);
    }
    friend Point operator+(Point lhs, const Point &rhs) {
        return lhs += rhs;
    }
    friend Point operator-(Point lhs, const Point &rhs) {
        return lhs -= rhs;
    }
    friend Point operator*(Point lhs, const T &rhs) {
        return lhs *= rhs;
    }
}p[4];
 
T dot(const Point &a, const Point &b) {
    return a.x * b.x + a.y * b.y;
}
 
T cross(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
}
void solve(){
	//try it again.
	int A,B,C,D;
	cin>>A>>B>>C>>D;
	p[0].x=A;p[0].y=B;
	p[2].x=C;p[2].y=D;
	p[1].x =((p[0].x+p[2].x)+(p[2].y-p[0].y))/2;
	p[1].y =((p[0].y+p[2].y)+(p[0].x-p[2].x))/2;
	p[3].x =((p[0].x+p[2].x)-(p[2].y-p[0].y))/2;
	p[3].y =((p[0].y+p[2].y)-(p[0].x-p[2].x))/2;
	if(dot(p[1]-p[0],p[1]-p[3])==0){
		cout<<p[1].x<<" "<<p[1].y<<endl;
	}
	else if(dot(p[3]-p[0],p[2]-p[3])==0){
		cout<<p[3].x<<" "<<p[3].y<<endl;
	}
	else cout<<"No Answer!";
}