头像

Heart_3




离线:24分钟前


最近来访(62)
用户头像
222222
用户头像
acwing_68271
用户头像
氚菜不辣
用户头像
Backlight
用户头像
柒月栗子
用户头像
宋霜辰
用户头像
xiaohuahua
用户头像
阿拉斯加海湾
用户头像
ζޓއ๓o北上少年
用户头像
11_
用户头像
fym
用户头像
花落烟雨迷离
用户头像
_Jyxml
用户头像
沉潜_0
用户头像
CanYuan
用户头像
超凶大魔王就是我
用户头像
批发人间烟火
用户头像
yxc
用户头像
acwing_9052
用户头像
WizCode


Heart_3
6天前
#include<bits/stdc++.h>

using namespace std;

double n, m;
using _T=double; // 全局数据类型,可修改为 long long 等

constexpr _T eps=1e-8;
constexpr long double PI=3.1415926535897932384l;
// 点与向量
template<typename T> struct point
{
  T x,y;

  bool operator==(const point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
  bool operator<(const point &a) const {if (abs(x-a.x)<=eps) return y<a.y-eps; return x<a.x-eps;}
  bool operator>(const point &a) const {return !(*this<a || *this==a);}
  point operator+(const point &a) const {return {x+a.x,y+a.y};}
  point operator-(const point &a) const {return {x-a.x,y-a.y};}
  point operator-() const {return {-x,-y};}
  point operator*(const T k) const {return {k*x,k*y};}
  point operator/(const T k) const {return {x/k,y/k};}
  T operator*(const point &a) const {return x*a.x+y*a.y;}  // 点积
  T operator^(const point &a) const {return x*a.y-y*a.x;}  // 叉积,注意优先级
  int toleft(const point &a) const {const auto t=(*this)^a; return (t>eps)-(t<-eps);}  // to-left 测试
  T len2() const {return (*this)*(*this);}  // 向量长度的平方
  T dis2(const point &a) const {return (a-(*this)).len2();}  // 两点距离的平方

  // 涉及浮点数
  long double len() const {return sqrtl(len2());}  // 向量长度
  long double dis(const point &a) const {return sqrtl(dis2(a));}  // 两点距离
  long double ang(const point &a) const {return acosl(max(-1.0,min(1.0,((*this)*a)/(len()*a.len()))));}  // 向量夹角
  point rot(const long double rad) const {return {x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};}  // 逆时针旋转(给定角度)
  point rot(const long double cosr,const long double sinr) const {return {x*cosr-y*sinr,x*sinr+y*cosr};}  // 逆时针旋转(给定角度的正弦与余弦)
};
template<typename T> struct line 
{
    point <T> p, v;
    // p 为直线上一点,v 为方向向量
    bool operator==(const line &a) const { return v.toleft(a.v) == 0 && v.toleft(p - a.p) == 0; }
    int toleft(const point <T> &a) const { return v.toleft(a - p); }
    // to-left 测试

    // 涉及浮点数
    point <T> inter(const line &a) const { return p + v * ((a.v ^ (p - a.p)) / (v ^ a.v)); }
    // 直线交点
    long double dis(const point <T> &a) const { return abs(v ^ (a - p)) / v.len(); }
    // 点到直线距离
    point <T> proj(const point <T> &a) const { return p + v * ((v * (a - p)) / (v * v)); }
    // 点在直线上的投影
};

vector<point<double>> convexhull(vector<point<double>> p)
{
    vector<point<double>> st;
    sort(p.begin(),p.end());
    const auto check=[](const vector<point<double>> &st,const point<double> &u)
    {
        const auto back1=st.back(),back2=*prev(st.end(),2);
        return (back1-back2).toleft(u-back2)<=0;
    };
    for (const point<double> &u:p)
    {
        while (st.size()>1 && check(st,u)) st.pop_back();
        st.push_back(u);
    }
    size_t k=st.size();
    p.pop_back(); reverse(p.begin(),p.end());
    for (const point<double> &u:p)
    {
        while (st.size()>k && check(st,u)) st.pop_back();
        st.push_back(u);
    }
    st.pop_back();
    return {st};
}

double check(const point<double> & u, const point<double>& v, const point<double>& p)
{
    line<double> uv = { u,v - u };
    if ((p - u) * (v - u) >= -eps && (p - v) * (u - v) >= -eps) return uv.dis(p);//如果点p在线段uv同一侧且投影点在uv之间那么直接返回p到uv距离
    return min(p.dis(u), p.dis(v));//否则依次判断up和pv距离
}

double caliper(const vector<point<double> >& a, const vector<point<double> >& b)//凸包间最短距离,边在a旋转,在b上找对踵点
{
    auto area = [](const point<double>& u, const point<double>& v, const point<double>& w) {return ((w - u) ^ (w - v)); };
    int j0 = 0;
    for (int j = 0; j < b.size(); j++)
    {
        if (area(a[0], a[1], b[j]) > area(a[0], a[1], b[j0]))j0 = j;
    }
    double dis = check(a[0], a[1], b[j0]);
    for (int i = 0, j = j0; i < a.size(); i++)
    {
        int nxti = (i + 1) % a.size(), nxtj = (j + 1) % b.size();
        dis = min(dis, check(a[i], a[nxti], b[j]));
        while (area(a[i], a[nxti], b[nxtj]) >= area(a[i], a[nxti], b[j])-eps)
        {
            j = nxtj;
            nxtj = (j + 1) % b.size();
            dis = min(dis, check(a[i], a[nxti], b[j]));
        }
    }
    return dis;
}

vector<point<double>> p1, p2;
/*
先得到两个凸包放于p1,p2然后对两个凸包用旋转卡壳求出p2上离p1最近的点,p1上离p2最近的点距离
*/
int main()
{
    while(cin >> n >> m, n || m)
    {
        vector<point<double> > temp1, temp2;
        for(int i = 0; i < n; i ++)
        {
            double x, y;
            cin >> x >> y;
            temp1.push_back({x, y});
        }
        for(int i = 0; i < m; i ++)
        {
            double x, y;
            cin >> x >> y;
            temp2.push_back({x, y});
        }
        p1 = convexhull(temp1);
        p2 = convexhull(temp2);
        printf("%.9lf\n", min(caliper(p1, p2), caliper(p2, p1)));
    }
    return 0;
}


活动打卡代码 AcWing 2938. 周游世界

Heart_3
10天前
/*
旋转卡壳求最远点对(可以发现最远点对一定是凸包上的两个点)
第一步求凸包
第二步对于凸包上的每个点,我们对于每一条边求一个距离该边最远的点,会发现这是一个具有凸性质的并且有对于下一条边最远的点会更远
如果这条边ab对于j点和j+1点,j到ab距离大于j+1点到ab距离那么j就是最远点不然继续更新,每次对于最远点与a,b两点求距离取min
j到ab的距离可以由ab与j的叉积求出,因为叉积求得是面积,在底边相同的情况,一个点离直线越远,面积越大
*/

#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 50010;


int n;
PII q[N];
int stk[N], top;
bool used[N];

PII operator- (PII a, PII b)
{
    return {a.x - b.x, a.y - b.y};
}

int operator* (PII a, PII b)
{
    return a.x * b.y - a.y * b.x;
}

int area(PII a, PII b, PII c)
{
    return (b - a) * (c - a);
}

int get_dist(PII a, PII b)
{
    int dx = a.x - b.x;
    int dy = a.y - b.y;
    return dx * dx + dy * dy;
}

void get_convex()
{
    sort(q, q + n);
    for (int i = 0; i < n; i ++ )
    {
        while (top >= 2 && area(q[stk[top - 2]], q[stk[top - 1]], q[i]) <= 0)
        {
            if (area(q[stk[top - 2]], q[stk[top - 1]], q[i]) < 0)
                used[stk[ -- top]] = false;
            else top -- ;
        }
        stk[top ++ ] = i;
        used[i] = true;
    }

    used[0] = false;
    for (int i = n - 1; i >= 0; i -- )
    {
        if (used[i]) continue;
        while (top >= 2 && area(q[stk[top - 2]], q[stk[top - 1]], q[i]) <= 0)
            top -- ;
        stk[top ++ ] = i;
    }
    top -- ;
}

int rotating_calipers()
{
    if (top <= 2) return get_dist(q[0], q[n - 1]);

    int res = 0;
    for (int i = 0, j = 2; i < top; i ++ )
    {
        auto d = q[stk[i]], e = q[stk[i + 1]];
        while (area(d, e, q[stk[j]]) < area(d, e, q[stk[j + 1]])) j = (j + 1) % top;
        res = max(res, max(get_dist(d, q[stk[j]]), get_dist(e, q[stk[j]])));
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &q[i].x, &q[i].y);
    get_convex();
    printf("%d\n", rotating_calipers());

    return 0;
}


活动打卡代码 AcWing 2938. 周游世界

Heart_3
10天前
/*
旋转卡壳求最远点对(可以发现最远点对一定是凸包上的两个点)
第一步求凸包
第二步对于凸包上的每个点,我们对于每一条边求一个距离该边最远的点,会发现这是一个具有凸性质的并且有对于下一条边最远的点会更远
如果这条边ab对于j点和j+1点,j到ab距离大于j+1点到ab距离那么j就是最远点不然继续更新,每次对于最远点与a,b两点求距离取min
*/

#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 50010;


int n;
PII q[N];
int stk[N], top;
bool used[N];

PII operator- (PII a, PII b)
{
    return {a.x - b.x, a.y - b.y};
}

int operator* (PII a, PII b)
{
    return a.x * b.y - a.y * b.x;
}

int area(PII a, PII b, PII c)
{
    return (b - a) * (c - a);
}

int get_dist(PII a, PII b)
{
    int dx = a.x - b.x;
    int dy = a.y - b.y;
    return dx * dx + dy * dy;
}

void get_convex()
{
    sort(q, q + n);
    for (int i = 0; i < n; i ++ )
    {
        while (top >= 2 && area(q[stk[top - 2]], q[stk[top - 1]], q[i]) <= 0)
        {
            if (area(q[stk[top - 2]], q[stk[top - 1]], q[i]) < 0)
                used[stk[ -- top]] = false;
            else top -- ;
        }
        stk[top ++ ] = i;
        used[i] = true;
    }

    used[0] = false;
    for (int i = n - 1; i >= 0; i -- )
    {
        if (used[i]) continue;
        while (top >= 2 && area(q[stk[top - 2]], q[stk[top - 1]], q[i]) <= 0)
            top -- ;
        stk[top ++ ] = i;
    }
    top -- ;
}

int rotating_calipers()
{
    if (top <= 2) return get_dist(q[0], q[n - 1]);

    int res = 0;
    for (int i = 0, j = 2; i < top; i ++ )
    {
        auto d = q[stk[i]], e = q[stk[i + 1]];
        while (area(d, e, q[stk[j]]) < area(d, e, q[stk[j + 1]])) j = (j + 1) % top;
        res = max(res, max(get_dist(d, q[stk[j]]), get_dist(e, q[stk[j]])));
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &q[i].x, &q[i].y);
    get_convex();
    printf("%d\n", rotating_calipers());

    return 0;
}


活动打卡代码 AcWing 2957. 赛车

Heart_3
30天前
总体思路是将所有赛车看成一个y = vx + b;
然后作图发现,如果加入x,y坐标,那么就是求所有直线的半平面交所用到的边,纪录即可

关键点一:可能有多辆赛车方程完全一致,那么需要将编号存储成不一样的,用map<pii, vector<int> >存,然后line结构体也放一个vector
用来存放直线被选,然后该直线代表多辆赛车,最后遍历每条被选的直线,并把他的ids(赛车编号)全存进ans,然后sort输出即可
关键点二:如果一个点是很多直线的交点,那么这个点代表这些赛车都领跑,那么把经过这个点的赛车都需要存起来,只需要在on_right函数里面
判定的时候return area(a.st, a.ed, o) < 0 ; 只删去bc直线交点在a直线右边这种情况即可
最后对ans   sort一下输出即可
#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LD, LD> PDD;
const long double eps = 1e-18;
const int N = 10010;
int n, cnt;

struct Line
{
    PDD st, ed;
    vector<int> ids;
}line[N];

int ki[N], vi[N];
int q[N], ans[N];

PDD operator-(PDD a, PDD b)
{
    return {a.x-b.x, a.y-b.y};
}

int sign(LD x)
{
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    return 1;
}

int dcmp(LD a, LD b)
{
    if(fabs(a-b) < eps)return 0;
    if(a < b)return -1;
    return 1;
}

LD cross(PDD a, PDD b)
{
    return a.x*b.y - a.y*b.x;
}

LD area(PDD a, PDD b, PDD c)
{
    return cross(b-a, c-a);
}

LD get_angle(Line a)
{
    return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x);
}

bool cmp(Line a, Line b)
{
    LD A = get_angle(a), B = get_angle(b);
    if(!dcmp(A, B))return area(a.st, a.ed, b.ed) < 0;
    return A < B;
}
//用点向式求出两个直线交点
PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w)
{
    auto u = p - q;
    LD t = cross(w, u) / cross(v, w);
    return {p.x + v.x * t, p.y + v.y * t};
}
//得到两条直线a,b的交点
PDD get_line_intersection(Line& a, Line& b)
{
    return get_line_intersection(a.st, a.ed - a.st, b.st, b.ed - b.st);
}
//判断bc交点o是否在a直线右边
bool on_right(Line a, Line b, Line c)
{
    auto o = get_line_intersection(b, c);
    return area(a.st, a.ed, o) < 0 ;
}

void half_plane_intersection()
{
    sort(line, line + cnt , cmp);
    int tt = -1, hh = 0;
    for(int i = 0; i < cnt ; i ++)
    {
        if(i && ! dcmp(get_angle(line[i]), get_angle(line[i-1])))continue;
        while(hh + 1 <= tt && on_right(line[i], line[q[tt - 1]], line[q[tt]]))tt --;
        while(hh + 1 <= tt && on_right(line[i], line[q[hh]], line[q[hh + 1]]))hh ++;
        q[++ tt] = i;
    }
    while(hh + 1 <= tt && on_right(line[q[hh]], line[q[tt - 1]], line[q[tt]])) tt --;
    while(hh + 1 <= tt && on_right(line[q[tt]], line[q[hh]], line[q[hh + 1]])) hh ++; 

    int k = 0;
    for(int i = hh; i <= tt ; i ++)
        for(auto id : line[q[i]].ids)
        {
            ans[k ++] = id;
        }
    sort(ans , ans + k);
    printf("%d\n", k);
    for(int i = 0; i < k ; i ++)
    {
        printf("%d ", ans[i]);
    }
    puts("");
}

int main()
{
    map<PII, vector<int> > ids;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)scanf("%d", &ki[i]);
    for(int i = 1; i <= n; i ++)scanf("%d", &vi[i]);
    for(int i = 1; i <= n; i ++)
        ids[{ki[i], vi[i]}].push_back(i);

    line[cnt ++] = {{0, 10000}, {0, 0}};
    line[cnt ++] = {{0, 0}, {10000, 0}};
    for(auto [k, v]:ids)
    {
        line[cnt ++] = {{0, k.x}, {1, k.x + k.y}, {v}};
    }
    half_plane_intersection();
    return 0;
}



Heart_3
30天前
总体思路是将所有赛车看成一个y = vx + b;
然后作图发现,如果加入x,y坐标,那么就是求所有直线的半平面交所用到的边,纪录即可

关键点一:可能有多辆赛车方程完全一致,那么需要将编号存储成不一样的,
用map<pii, vector<int> >存,然后line结构体也放一个vector
用来存放直线被选,然后该直线代表多辆赛车,最后遍历每条被选的直线
并把他的ids(赛车编号)全存进ans,然后sort输出即可

关键点二:如果一个点是很多直线的交点,那么这个点代表这些赛车都领跑,
那么把经过这个点的赛车都需要存起来,只需要在on_right函数里面
判定的时候return area(a.st, a.ed, o) < 0 ; 只删去bc直线交点在a直线右边这种情况即可

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LD, LD> PDD;
const long double eps = 1e-18;
const int N = 10010;
int n, cnt;

struct Line
{
    PDD st, ed;
    vector<int> ids;
}line[N];

int ki[N], vi[N];
int q[N], ans[N];

PDD operator-(PDD a, PDD b)
{
    return {a.x-b.x, a.y-b.y};
}

int sign(LD x)
{
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    return 1;
}

int dcmp(LD a, LD b)
{
    if(fabs(a-b) < eps)return 0;
    if(a < b)return -1;
    return 1;
}

LD cross(PDD a, PDD b)
{
    return a.x*b.y - a.y*b.x;
}

LD area(PDD a, PDD b, PDD c)
{
    return cross(b-a, c-a);
}

LD get_angle(Line a)
{
    return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x);
}

bool cmp(Line a, Line b)
{
    LD A = get_angle(a), B = get_angle(b);
    if(!dcmp(A, B))return area(a.st, a.ed, b.ed) < 0;
    return A < B;
}
//用点向式求出两个直线交点
PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w)
{
    auto u = p - q;
    LD t = cross(w, u) / cross(v, w);
    return {p.x + v.x * t, p.y + v.y * t};
}
//得到两条直线a,b的交点
PDD get_line_intersection(Line& a, Line& b)
{
    return get_line_intersection(a.st, a.ed - a.st, b.st, b.ed - b.st);
}
//判断bc交点o是否在a直线右边
bool on_right(Line a, Line b, Line c)
{
    auto o = get_line_intersection(b, c);
    return area(a.st, a.ed, o) < 0 ;
}

void half_plane_intersection()
{
    sort(line, line + cnt , cmp);
    int tt = -1, hh = 0;
    for(int i = 0; i < cnt ; i ++)
    {
        if(i && ! dcmp(get_angle(line[i]), get_angle(line[i-1])))continue;
        while(hh + 1 <= tt && on_right(line[i], line[q[tt - 1]], line[q[tt]]))tt --;
        while(hh + 1 <= tt && on_right(line[i], line[q[hh]], line[q[hh + 1]]))hh ++;
        q[++ tt] = i;
    }
    while(hh + 1 <= tt && on_right(line[q[hh]], line[q[tt - 1]], line[q[tt]])) tt --;
    while(hh + 1 <= tt && on_right(line[q[tt]], line[q[hh]], line[q[hh + 1]])) hh ++; 

    int k = 0;
    for(int i = hh; i <= tt ; i ++)
        for(auto id : line[q[i]].ids)
        {
            ans[k ++] = id;
        }
    sort(ans , ans + k);
    printf("%d\n", k);
    for(int i = 0; i < k ; i ++)
    {
        printf("%d ", ans[i]);
    }
    puts("");
}

int main()
{
    map<PII, vector<int> > ids;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)scanf("%d", &ki[i]);
    for(int i = 1; i <= n; i ++)scanf("%d", &vi[i]);
    for(int i = 1; i <= n; i ++)
        ids[{ki[i], vi[i]}].push_back(i);

    line[cnt ++] = {{0, 10000}, {0, 0}};
    line[cnt ++] = {{0, 0}, {10000, 0}};
    for(auto [k, v]:ids)
    {
        line[cnt ++] = {{0, k.x}, {1, k.x + k.y}, {v}};
    }
    half_plane_intersection();
    return 0;
}


活动打卡代码 AcWing 2803. 凸多边形

Heart_3
1个月前
求半平面交步骤:

将所有边按角度排序
利用双端队列存储直线,正向遍历所有边
检查队尾直线和队尾前一条的交点是否在当前边的右边,如果在右边,则将队尾元素踢出队列
对于队头重复3
最后队列中的所有直线就是构成最终半平面交的边集
相邻两边的交点就是最终半平面交的所有顶点
#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 = 510;
const double eps = 1e-8;

int cnt;
struct Line
{
    PDD st, ed;
}line[N];
PDD pg[N], ans[N];
int q[N];

int sign(double x)
{
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}

int dcmp(double x, double y)//判断两个double是否相等
{
    if (fabs(x - y) < eps) return 0;
    if (x < y) return -1;
    return 1;
}

double get_angle(const Line& a)//求向量a的角度atan(y,x)
{
    return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x);
}

PDD operator-(PDD a, PDD b)
{
    return {a.x - b.x, a.y - b.y};
}

double cross(PDD a, PDD b)
{
    return a.x * b.y - a.y * b.x;
}

double area(PDD a, PDD b, PDD c)
{
    return cross(b - a, c - a);
}

//排序的cmp函数,
bool cmp(const Line& a, const Line& b)
{
    double A = get_angle(a), B = get_angle(b);
    if (!dcmp(A,  B)) return area(a.st, a.ed, b.ed) < 0;
    //如果角度相等,把更靠左的放到前面,
    //可以发现a×b,小于0代表a在b的逆时针方向,即a在左边,返回true
    return A < B;
}

PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w)//
{
    //知道直线点向式,起点p向量v跟起点q向量w,得到两个直线交点放法
    auto u = p - q;
    double t = cross(w, u) / cross(v, w);
    return {p.x + v.x * t, p.y + v.y * t};
}

PDD get_line_intersection(Line a, Line b)//求两个直线的交点
{
    //分别传进去两条直线的一个点,然后传进去这个直线的向量
    return get_line_intersection(a.st, a.ed - a.st, b.st, b.ed - b.st);
}

// bc的交点是否在a的右侧
bool on_right(Line& a, Line& b, Line& c)
{
    auto o = get_line_intersection(b, c);//o为bc直线交点,判断是否在a右侧
    return sign(area(a.st, a.ed, o)) <= 0;
}

/*思路是每次先将所有直线按角度sort,如果有一样的角度,越左边的排前面
 用一个双端队列进行存储所选取的边,遇到一个新的直线,判断队尾两条直线交点与当前直线位置
 如果交点在直线右边那么队尾直线可以去掉(画图可以看出)
 队头队尾都需要判断,相同操作, 然后每次将当前点塞入队列

 然后再用队尾去更新队头,用队头去更新队尾
 最后计算结果是所有选取的直线的交点所围成的面积,先将队头放进到队尾形成闭环,然后每次找两个直线的交点存起来
 最后用求多边形面积(不一定是凸多边形)
        我们可以从第一个顶点除法把凸多边形分成n − 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;
        }
    求出面积
*/
double half_plane_intersection()
{
    sort(line, line + cnt, cmp);
    int hh = 0, tt = -1;
    for (int i = 0; i < cnt; i ++ )
    {
        //遍历过程中,如果前后直线角度一样,那么后面这条必然可以不选
        if (i && !dcmp(get_angle(line[i]), get_angle(line[i - 1]))) continue;
        while (hh + 1 <= tt && on_right(line[i], line[q[tt - 1]], line[q[tt]])) tt -- ;
        while (hh + 1 <= tt && on_right(line[i], line[q[hh]], line[q[hh + 1]])) hh ++ ;
        q[ ++ tt] = i;
    }
    while (hh + 1 <= tt && on_right(line[q[hh]], line[q[tt - 1]], line[q[tt]])) tt -- ;
    while (hh + 1 <= tt && on_right(line[q[tt]], line[q[hh]], line[q[hh + 1]])) hh ++ ;

    q[ ++ tt] = q[hh];
    int k = 0;
    for (int i = hh; i < tt; i ++ )
        ans[k ++ ] = get_line_intersection(line[q[i]], line[q[i + 1]]);
    double res = 0;
    for (int i = 1; i + 1 < k; i ++ )
        res += area(ans[0], ans[i], ans[i + 1]);
    return res / 2;
}

int main()
{
    int n, m;
    scanf("%d", &n);
    while (n -- )
    {
        scanf("%d", &m);
        for (int i = 0; i < m; i ++ ) scanf("%lf%lf", &pg[i].x, &pg[i].y);
        for (int i = 0; i < m; i ++ )
            line[cnt ++ ] = {pg[i], pg[(i + 1) % m]};
    }
    double res = half_plane_intersection();
    printf("%.3lf\n", res);

    return 0;
}



活动打卡代码 AcWing 2935. 信用卡凸包

Heart_3
1个月前
题意:给你n张长a宽b的卡片的中心坐标,卡片四个角是小圆弧,以及旋转角度,求将n个卡片组合起来的区域,用线框住所需最小线长
可以发现其实就是对每个圆圆心求一个凸包,然后再加上一个圆的周长
那么难点在于通过n张卡片中心坐标以及旋转角度,x,y,z求出四个圆心坐标,
当卡片平放的时候可以很容易得出四个角坐标,我们只需要在四个角坐标上减去r就可以得到四个圆心,
(x+b/2,y+a/2), (x-b/2, y+a/2), (x-b/2,y-a/2), (x+b/2, y-a/2)
然后再用公式得到顺时针旋转z°后的坐标,对其求凸包即可,因为公式是顺时针旋转z°的角度,那么逆时针使用-z°即可
公式为{a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)};  
(x,y)(cosb, -sinb) 矩阵相乘
        (sinb,  cosb)
#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 = 40010;
const double pi = acos(-1);

int n, cnt;
PDD q[N];
int stk[N], top;
bool used[N];

PDD rotate(PDD a, double b)
{
    return {a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)};
}

PDD operator- (PDD a, PDD b)
{
    return {a.x - b.x, a.y - b.y};
}

double cross(PDD a, PDD b)
{
    return a.x * b.y - a.y * b.x;
}

double area(PDD a, PDD b, PDD c)
{
    return cross(b - a, c - a);
}

double get_dist(PDD a, PDD b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

double andrew()
{
    sort(q, q + cnt);
    for (int i = 0; i < cnt; i ++ )
    {
        while (top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) <= 0)
        {
            // 凸包边界上的点即使被从栈中删掉,也不能删掉used上的标记
            if (area(q[stk[top - 1]], q[stk[top]], q[i]) < 0)
                used[stk[top -- ]] = false;
            else top -- ;
        }
        stk[ ++ top] = i;
        used[i] = true;
    }
    used[0] = 0;
    for (int i = cnt - 1; i >= 0; i -- )
    {
        if (used[i]) continue;
        while (top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) <= 0)
            top -- ;
        stk[ ++ top] = i;
    }

    double res = 0;
    for (int i = 2; i <= top; i ++ )
        res += get_dist(q[stk[i - 1]], q[stk[i]]);
    return res;
}

int main()
{
    scanf("%d", &n);
    double a, b, r;
    scanf("%lf%lf%lf", &a, &b, &r);
    a = a / 2 - r, b = b / 2 - r;
    int dx[] = {1, 1, -1, -1}, dy[] = {1, -1, -1, 1};
    while (n -- )
    {
        double x, y, z;
        scanf("%lf%lf%lf", &x, &y, &z);
        for (int i = 0; i < 4; i ++ )
        {
            auto t = rotate({dx[i] * b, dy[i] * a}, -z);
            q[cnt ++ ] = {x + t.x, y + t.y};
        }
    }

    double res = andrew();
    printf("%.2lf\n", res + 2 * pi * r);

    return 0;
}


活动打卡代码 AcWing 1401. 围住奶牛

Heart_3
1个月前
#基础知识#
叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系:
若 P × Q > 0 , 则P在Q的顺时针方向。
若 P × Q < 0 , 则P在Q的逆时针方向。
若 P × Q = 0 , 则P与Q共线,但可能同向也可能反向
凸包问题的解决思路是先sort一下所有点,以x坐标为第一关键字sort
从左到右构建上凸包,然后从右往左构建下凸包
构建上凸包的时候如果用过的点就用used标记为true,用stk来存用选取了的点
(注意如果有点在凸包边界,那么不选也要标记为使用过)
上凸包构建完以后,构建下凸包的时候要把第一个点标记为没用过,形成闭环
(上下凸包顺序也可以倒过来求)
求上凸包的过程为,栈中有两个元素分别为a,b,然后如果当前结点c, 如果ac在ab的左边,那么代表b可以删去,(画图就能明白)
判断ab是否在ac右边,只需要对ab,ac向量求叉积即可,若ab × ac > 0 ab在ac的顺时针方向,则ab在ac的右边那么删去b点
然后将c点入栈,标记为使用过
#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 = 10010;

int n;
pdd q[N];
int stk[N];
bool used[N];

double get_dist(pdd a, pdd b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx*dx + dy*dy);
}

pdd operator-(pdd a, pdd b)
{
    return {a.x-b.x, a.y-b.y};
}

double cross(pdd a, pdd b)
{
    return (a.x * b.y - a.y * b.x);
}

double area(pdd a, pdd b, pdd c)
{
    return cross(b - a, c - a);
}

double andrew()
{
    sort(q, q + n);
    int top = 0;
    for (int i = 0; i < n; i ++ )
    {
        while (top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) >= 0)
        {
            // 凸包边界上的点即使被从栈中删掉,也不能删掉used上的标记
            if (area(q[stk[top - 1]], q[stk[top]], q[i]) > 0)
                used[stk[top -- ]] = false;
            else top -- ;
        }
        stk[ ++ top] = i;
        used[i] = true;
    }
    used[0] = false;
    for (int i = n - 1; i >= 0; i -- )
    {
        if (used[i]) continue;
        while (top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) >= 0)
            top -- ;
        stk[ ++ top] = i;
    }

    double res = 0;
    for (int i = 2; i <= top; i ++ )
        res += get_dist(q[stk[i - 1]], q[stk[i]]);
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0 ; i < n; i ++)scanf("%lf%lf", &q[i].x, &q[i].y);
    double res = andrew();
    printf("%.2lf\n", res);
    return 0;
}


活动打卡代码 AcWing 2984. 线段

Heart_3
1个月前
题意为一共n条线,判断是否存在一条直线满足将这 n 条线段投影到该直线上后,
所有的投影线段至少具有一个公共点,
如果找到一条线穿过所有直线,则答案存在
寻找方式就是(on²)遍历所有线的两个端点,形成的一条直线,
然后判断这条直线有没有穿过所有直线(on) 
通过a[i],b[i]这n条直线端点分别与q[i],q[j]这条直线向量叉乘
sign(area(q[i], q[j], a[k])) * sign(area(q[i], q[j], b[k])) > 0 
代表a[k],b[k]都在直线一端不符合
复杂度就是(on³)
#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];//q数组用来存每个点坐标,a[i],b[i]代表第i条直线

int sign(double x)
{
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    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;
}

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;
}


活动打卡代码 AcWing 2983. 玩具

Heart_3
1个月前
#基础知识#
叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系:
若 P × Q > 0 , 则P在Q的顺时针方向。
若 P × Q < 0 , 则P在Q的逆时针方向。
若 P × Q = 0 , 则P与Q共线,但可能同向也可能反向
将上顶点放入pair<ll ,ll> a中
下顶点放入b
然后二分判断每个玩具在那个区间  ans[区间]++;
二分的过程为判断这个点在所有直线的哪边
找到一个位置满足该点左边直线与其叉乘全小于0,右边直线叉乘全大于0
因为如果一个点和一条直线如图叉乘后结果为正,代表这个点c在直线ab左侧。

111.png

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
#define x first
#define y second
typedef long long ll;
typedef pair<ll, ll> pll;
const int N = 5010;
pll a[N], b[N];
ll ans[N];
int n, m;

ll cross(ll x1, ll y1, ll x2, ll y2)
{
     return x1 * y2 - x2 * y1;
}
//求一个三角形如图所示,求他的面积是否为正,
//即求ab向量叉乘ac向量如果大于0则面积为正,则证明c在ab直线左边
bool check(pll a, pll b, pll c)//a是上顶点
{
    if(cross(b.x-a.x, b.y-a.y, c.x-a.x, c.y-a.y) > 0) return true;
    else return false;
}

ll find(ll x, ll y)
{
    int l = 0, r = n;
    while(l < r)
    {
        int mid = (l + r)/2;
        if(check(b[mid], a[mid], {x, y}))r = mid;
        else l = mid + 1;
    }
    return r;
}

int main()
{
    bool f = 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 ++)
        {
            int l, r;
            cin >> l >> r;
            a[i] = {l, y1}, b[i] = {r, y2};
        }
        a[n] = {x2, y1}, b[n] = {x2, y2};

        if (f) f = false;
        else puts("");
        memset(ans, 0, sizeof ans);
        for(int i = 0; i < m; i ++)
        {
            int x1, y1;
            cin >> x1 >> y1;
            ans[find(x1, y1)] ++;
        }
        for(int i = 0; i <= n; i ++)
        {
            printf("%d: %d\n", i, ans[i]);
        }
    }
    return 0;
}