模板题,T了最后三个点
查看原帖
模板题,T了最后三个点
105820
阿尔托莉雅丶楼主2022/4/14 13:12
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;   //remember to modify the range of the data!!
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int maxp = 1e6 + 5;
const double Pi = acos(-1.0);
const double eps = 1e-10;
// #define double long double //开的时候注意输入输出用 %Lf

int n, m, T;

int sgn(double x)
{
    if(fabs(x) < eps)
        return 0;
    if(x > 0)
        return 1;
    else
        return -1;
}
//向量或者点
struct Point
{
    double x, y;
    Point() {};//构造函数
    Point(double a, double b): x(a), y(b) {};
    void input()
    {
        scanf("%lf%lf", &x, &y);
    }
    void write()
    {
        printf("%.8f %.8f\n", x, y);
    }
    bool operator == (const Point rhs) const
    {
        return sgn(x - rhs.x) == 0 && sgn(y - rhs.y) == 0;
    }
    bool operator < (const Point rhs) const //按x轴升序,x相同时按y升序
    {
        return sgn(x - rhs.x) == 0 ? sgn(y - rhs.y) < 0 : x < rhs.x;
    }
    Point operator + (const Point rhs) const //加法
    {
        return Point(x + rhs.x, y + rhs.y);
    }
    Point operator - (const Point rhs) const //减法
    {
        return Point(x - rhs.x, y - rhs.y);
    }
    double operator ^ (const Point rhs) const //向量叉积
    {
        return x * rhs.y - y * rhs.x;
    }
    double operator * (const Point rhs) const //向量点积
    {
        return x * rhs.x + y * rhs.y;
    }
    Point operator * (const double rhs) const //数量乘
    {
        return Point(x * rhs, y * rhs);
    }
    Point operator / (const double rhs) const //数量除法
    {
        return Point(x / rhs, y / rhs);
    }
    //返回向量模长
    double len()
    {
        return hypot(x,y);//库函数计算sqrt(x * x + y * y)
    }
    //返回向量模长的平方
    double len2() 
    {
        return x * x + y * y;
    }
    //将向量转化为长度为r的向量方向不变
    Point trunc(double r)
    {
        double l = len();
        if(!sgn(l))
            return *this;
        r /= l;
        return Point(x * r, y * r);
    }
    //向量顺时针旋转90度
    Point clockwiseRot()
    {
        return Point(y, -x);
    }
    //向量逆时针旋转90度
    Point anticlockwiseRot()
    {
        return Point(-y, x);
    }
    //向量逆时针旋转theta度(弧度制)
    Point rotate(double theta)
    {
        double c = cos(theta), s = sin(theta);
        return Point(x * c - y * s, x * s + y * c);
    }
    //点绕p点逆时针旋转theta度(弧度制)
    Point rotate(Point p, double theta)
    {
        Point v = (*this) - p;
        double c = cos(theta), s = sin(theta);
        return Point(p.x + v.x * c - v.y * s, p.y + v.x * s + v.y * c);
    }
    //两点之间的距离
    double distance (const Point rhs)
    {
        return hypot(x - rhs.x, y - rhs.y);
    }
    //两向量的夹角(弧度制)
    double rad(const Point rhs)
    {
        return fabs(atan2(fabs((*this) ^ rhs), (*this) * rhs));
    }
    bool quadrant(void) const //判断是否在一四象限含x正半轴和y负半轴
    {
        return y > 0 || (y == 0 && x >= 0);
    }
};
//直线或线段
struct Line
{
    Point s, e; //s起点, e终点
    Line() {}; //构造函数
    Line(Point s, Point e) : s(s), e(e) {};
    Line(double x1, double y1, double x2, double y2) : s(Point(x1, y1)), e(Point(x2, y2)) {}; 
    //根据一个点和倾斜角 theta(弧度) 确定直线,0 <= angle < Pi
    Line(Point p, double theta)
    {
        s = p;
        if(sgn(theta - Pi / 2) == 0) //垂直x轴
            e = s + Point(0, 1);
        else
            e = s + Point(1, tan(theta));
    }
    //ax + by + c = 0
    Line(double a, double b, double c)
    {
        if(sgn(a) == 0) //垂直y轴
            s = Point(0, - c / b), e = Point(1, - c / b);
        else if(sgn(b) == 0) //垂直x轴
            s = Point(- c / a, 0), e = Point(- c / a, 1);
        else 
            s = Point(0, -c / b), e = Point(1, (-c - a) / b);
    }
    void input()
    {
        scanf("%lf%lf%lf%lf", &s.x, &s.y, &e.x, &e.y);
    }
    void write()
    {
        printf("%.5f %.5f %.5f %.5f\n", s.x, s.y, e.x, e.y);
    }
    //x小的在前面,相同时y小的在前面
    void adjust()
    {
        if(e < s)
            swap(e, s);
    }
    //线段求长度
    double lenth()
    {
        return s.distance(e);
    }
    //返回直线的倾斜角 0<= angle <pi
    double angle() 
    {
        double k = atan2(e.y - s.y, e.x - s.x);
        if(sgn(k) < 0)
            k += Pi;
        if(sgn(k - Pi) == 0)
            k -= Pi;
        return k;
    }
    //点和直线关系 1左边,2右边,3在线上
    //左边是指向量srhs与se叉积为负数所以与s,e点的顺序有关
    int relation(Point rhs)
    {
        int c = sgn((rhs - s) ^ (e - s));
        if(c < 0)
            return 1;
        if(c > 0)
            return 2;
        return 3;
    }
    // 点在线段上的判断
    bool pointOnSeg(Point rhs)
    {
        return sgn((rhs - s) ^ (e - s)) == 0 && sgn((rhs - s) * (rhs - e)) <= 0;
    }
    //判断两直线平行或重合
    //重合是特殊的平行关系
    bool parallel(Line rhs)
    {
        return sgn((e - s) ^ (rhs.e - rhs.s)) == 0;
    }
    //判断两直线是否垂直
    bool vertical(Line rhs)
    {
        return ((e - s) * (rhs.e - rhs.s)) == 0;
    }
    //两线段相交判断 0不相交 1非规范相交 2规范相交
    int segCrossSeg(Line rhs)
    {
        int d1 = sgn((e - s) ^ (rhs.s - s)), d2 = sgn((e - s) ^ (rhs.e - s));
        int d3 = sgn((rhs.e - rhs.s) ^ (s - rhs.s)), d4 = sgn((rhs.e - rhs.s)^(e - rhs.s));
        if( (d1 ^ d2) == -2 && (d3 ^ d4) == -2) //当前线段端点在另线段两边
            return 2;
        return  (d1 == 0 && sgn((rhs.s - s) * (rhs.s - e)) <= 0) ||
                (d2 == 0 && sgn((rhs.e - s) * (rhs.e - e)) <= 0) || 
                (d3 == 0 && sgn((s - rhs.s) * (s - rhs.e)) <= 0) ||
                (d4 == 0 && sgn((e - rhs.s) * (e - rhs.e)) <= 0);
    }
    //直线和线段相交判断 0不相交 1非规范相交 2规范相交
    //-*this line -rhs seg
    int lineCrossSeg(Line rhs)
    {
        int d1 = sgn((e - s) ^ (rhs.s - s));
        int d2 = sgn((e - s) ^ (rhs.e - s));
        if((d1 ^ d2) == -2)
            return 2;
        return d1 == 0 || d2 == 0;
    }
    //两直线关系 0平行 1重合 2垂直 3非垂直相交
    int relation(Line rhs)
    {
        if(parallel(rhs))
            return rhs.relation(s) == 3;
        if(vertical(rhs))
            return 2;
        return 3;
    }
    //求两直线的交点 要保证两直线不平行或重合
    Point crossPoint(Line rhs)
    {
        double s1 = (rhs.e - rhs.s) ^ (s - rhs.s);
        double s2 = (rhs.e - rhs.s) ^ (e - rhs.s);
        if(rhs.s == s && rhs.e == e)
            cout << "?\n";
        return Point((s.x * s2 - e.x * s1) / (s2 - s1), (s.y * s2 - e.y * s1) / (s2 - s1));
    }
    //点到直线的距离
    double disPointtoLine(Point rhs)
    {
        return fabs((rhs - s) ^ (e - s)) / lenth();
    }
    //点到线段的距离
    double disPointtoSeg(Point rhs)
    {
        if(sgn((rhs - s) * (e - s)) < 0 || sgn((rhs - e) * (s - e) < 0))
            return min(rhs.distance(s), rhs.distance(e));
        return disPointtoLine(rhs);
    }
    //线段到线段的距离 相交时距离为零
    double disSegtoSeg(Line rhs)
    {
        if(segCrossSeg(rhs) != 0)
            return 0.0;
        return min(min(disPointtoSeg(rhs.s), disPointtoSeg(rhs.e)), min(rhs.disPointtoSeg(s), rhs.disPointtoSeg(e)));
    }
    //点 p 在直线上的投影
    Point lineProjection(Point rhs)
    {
        return s + ((e - s) * ((e - s) * (rhs - s)) / (e - s).len2());
    }
    //点 p 关于直线的对称点
    Point symmetryPoint(Point rhs)
    {
        Point q = lineProjection(rhs);
        return Point(2 * q.x - rhs.x, 2 * q.y - rhs.y);
    }
};
//多边形
struct polygon
{
    int n;
    Point p[maxp];
    //极角排序
    //以最左边的点(x相同时取最下面的)为原点
    void norm(void)
    {
        Point mi = p[0];
        for(int i = 1; i < n; i++)
            mi = min(mi, p[i]);
        sort(p, p + n, [&](Point a, Point b){
            int d = sgn((a - mi) ^ (b - mi));
            if(d == 0)
                return sgn(a.distance(mi) - b.distance(mi)) > 0;
            return d > 0;
        });
    }
    //以原点为极点的极角排序
    void polarsort(void)
    {
        sort(p, p + n, [](Point a, Point b){
            if(a.quadrant() ^ b.quadrant())//如果象限不同
                return a.quadrant() > b.quadrant();
            return sgn(a ^ b) > 0;
        });
    }

    //凸包 需要极角排序
    void Graham(polygon &convex)
    {
        norm();
        int &top = convex.n;
        top = 0;
        if(n == 1)
        {
            top = 1;
            convex.p[0] = p[0];
            return ;
        }
        if(n == 2)
        {
            top = 2;
            convex.p[0] = p[0];
            convex.p[1] = p[1];
            if(p[0] == p[1])
                top--;
            return;
        }
        convex.p[0] = p[0];
        convex.p[1] = p[1];
        top = 2;
        for(int i = 2; i < n; i++)
        {
            while(top > 1 && sgn((convex.p[top - 1] - convex.p[top - 2]) ^ (p[i] - convex.p[top - 2])) <= 0)
                top--;
            convex.p[top++] = p[i];
        }
        if(top == 2 && convex.p[0] == convex.p[1]) //特判
            top--;
    }
    //凸包 需要排序
    void Andrew(polygon &convex)
    {
        sort(p, p + n);
        convex.n = n;
        for(int i = 0; i < min(n, 2); i++)
            convex.p[i] = p[i];
        if(convex.n == 2 && convex.p[0] == convex.p[1])
            convex.n--;
        if(n <= 2)
            return;
        int &top = convex.n = 0;
        for(int i = 0; i < n; convex.p[top++] = p[i++])
            while(top >= 2 && sgn((convex.p[top - 1] - convex.p[top - 2]) ^ (p[i] - convex.p[top - 1])) <= 0)
                top--;
        for(int i = n - 2, tem = top + 1; i >= 0; convex.p[top++] = p[i--])
            while(top >= tem && sgn((convex.p[top - 1] - convex.p[top - 2]) ^ (p[i] - convex.p[top - 1])) <= 0)
                top--;
        top--; //需要减一,因为第一个点会入两次
        if(top == 2 && convex.p[0] == convex.p[1]) //特判
            top--;
    }
    //点和多边形的关系 3点上 2边上 1内部 0外部
    int relation(Point rhs)
    {
        for(int i = 0; i < n; i++)
            if(rhs == p[i])
                return 3;
        for(int i = 0; i < n; i++)
            if(Line(p[i], p[(i + 1) % n]).pointOnSeg(rhs))
                return 2;
        int cnt = 0;
        for(int i = 0; i < n; i++)
        {
            int j = (i + 1) % n;
            int k = sgn((rhs - p[j]) ^ (p[i] - p[j]));
            int u = sgn(p[i].y - rhs.y);
            int v = sgn(p[j].y - rhs.y);
            if(k > 0 && u < 0 && v >= 0)
                cnt++;
            if(k < 0 && v < 0 && u >= 0)
                cnt--;
        }
        return cnt != 0;
    }
};


//凸包a, b的闵可夫斯基和结果存在res里
//多个时可以全部边一起求(需重构)
void Minkowski(polygon &tem, polygon &res, polygon const &a, polygon const &b)
{
    // 得到两个凸包的向量集
    vector <Point> va, vb;
    for(int i = 0; i < a.n; i++) 
        va.push_back(a.p[(i + 1) % a.n] - a.p[i]);
    for(int i = 0; i < b.n; i++) 
        vb.push_back(b.p[(i + 1) % b.n] - b.p[i]);
    int &n = tem.n;
    n = 0;
    tem.p[n++] = a.p[0] + b.p[0];
    int l1 = 0, l2 = 0;

    while(l1 < a.n && l2 < b.n) 
        tem.p[n] = tem.p[n - 1] + ((va[l1] ^ vb[l2]) > 0 ? va[l1++] : vb[l2++]), n++;
    while(l1 < a.n) 
        tem.p[n] = tem.p[n - 1] + va[l1++], n++;
    while(l2 < b.n)
        tem.p[n] = tem.p[n - 1] + vb[l2++], n++;
    tem.Andrew(res);
}

polygon tem, ans, a, b, cona, conb;

int main(void)
{
    int q;
    cin >> a.n >> b.n >> q;

    for(int i = 0; i < a.n; i++)
        a.p[i].input();
    for(int i = 0; i < b.n; i++)
    {
        b.p[i].input();
        b.p[i].x = -b.p[i].x;
        b.p[i].y = -b.p[i].y;
    }
    a.Andrew(cona), b.Andrew(conb);
    Minkowski(tem, ans, cona, conb);
    while(q--)
    {
        Point w;
        w.input();
        cout << (ans.relation(w) == 0 ? 0 : 1) << '\n';
    }
    return 0;
}
2022/4/14 13:12
加载中...