链接

题目大意

思路

以为点积可以进行结合律，所以将b乘进去,得到

也就是 求一条有向直线，使得 A1, A2, ..., An 在直线上的投影是单调的。 首先可以看出，答案只与直线的方向向量有关，直线的位置可以是任意的，即输 出的前两个数是任意的。 • 对于相邻两个点，如果要在有向直线单调，那么直线的方向向量会被限制在一个 180°的范围内。 • 对于所有相邻的两点，求出其对应的限制范围，将所有的范围求交，交集中选出 一个向量即可。如果交集为空，则不存在。

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e5+5;
int n;
struct Point{
    double x,y;
    double operator ^(const Point &b)const{
        return x*b.y - y*b.x;
    }
};
Point p[maxn];
Point l,r;
Point L,R;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lf %lf",&p[i].x,&p[i].y);
    }
    L.x=L.y=1;
    for(int i=2;i<=n;i++){
        Point pp;
        pp.x=p[i].x-p[i-1].x;
        pp.y=p[i].y-p[i-1].y;
        if(pp.x==0&&pp.y==0) continue;
        r.y=-pp.x;
        l.x=-pp.y;
        l.y=pp.x;
        r.x=pp.y;
        if(i==2){
            L=l,R=r;
            continue;
        }
        if((l^R)>0&&(r^L)<0){
            printf("NO\n");
            return 0;
        }
        if((l^L)>0)L=l;
        if((r^R)<0)R=r;
    }
    printf("YES\n"); cout<<"0 0 ";
    cout<<L.x<<" "<<L.y;
}