首页 > 其他分享 >P4423 / YC271A [ 20240411 CQYC省选模拟赛 T1 ] 三角形(triangle)

P4423 / YC271A [ 20240411 CQYC省选模拟赛 T1 ] 三角形(triangle)

时间:2024-04-18 21:55:29浏览次数:28  
标签:pii triangle 省选 double T1 int edge ans include

题意

给定 \(n\) 个点,求平面最小三角形周长。

Sol

其实挺简单一算法,一直没学。

先随机转个∠,然后按照 \(x\) 排序。

考虑分治。

注意到分治左右两边的答案对当前可用的区间有限制。

将满足限制的点按照 \(y\) 排序。

这里可以归并做到一只 \(log\)。

然后集中注意力,发现对于每个点有用的节点有限制,暴力弄出右端点乱跑一下即可。

关于复杂度,注意到由于分治左右两边的答案,对于当前 \(h\) 大小的正方形里的点有限制。

因此枚举到的答案集合大小是 \(n\) 的常数级的。

所以复杂度为 \(O(n \log n)\)。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <cmath>
#include <vector>
#include <random>
#include <chrono>
#define pii pair <double, double>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
    int p = 0, flg = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') flg = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        p = p * 10 + c - '0';
        c = getchar();
    }
    return p * flg;
}
void write(int x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
bool _stmer;

#define fi first
#define se second

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const int N = 1e6 + 5;
array <pii, N> edge;

double fpow(double x) { return x * x; }

double dist(pii x, pii y) {
    double _x = fpow(x.fi - y.fi), _y = fpow(x.se - y.se);
    return sqrt(_x + _y);
}

double per(pii x, pii y, pii z) { return dist(x, y) + dist(y, z) + dist(x, z); }

double solve(int l, int r) {
    double ans = 4e18;
    if (r - l <= 3) {
        for (int i = l; i <= r; i++)
            for (int j = i + 1; j <= r; j++)
                for (int k = j + 1; k <= r; k++)
                    ans = min(ans, per(edge[i], edge[j], edge[k]));
        sort(edge.begin() + l, edge.begin() + r + 1, [](pii x, pii y) {
            return x.se < y.se;
        });
        return ans;
    }
    int mid = (l + r) >> 1, res = edge[mid].fi;
    ans = min(solve(l, mid), ans);
    ans = min(solve(mid + 1, r), ans);
    inplace_merge(edge.begin() + l, edge.begin() + 1 + mid,
                  edge.begin() + 1 + r, [](pii x, pii y) {
        return x.se < y.se;
    });
    vector <pii> tp;
    for (int i = l; i <= r; i++)
        if (abs(edge[i].fi - res) <= ans / 2.0)
            tp.push_back(edge[i]);
    for (int i = 0; i < (int)tp.size(); i++)
        for (int j = i + 1; j < (int)tp.size() && tp[j].se - tp[i].se <= ans / 2.0; j++)
            for (int k = i + 1; k < j; k++)
                ans = min(ans, per(tp[i], tp[j], tp[k]));
    return ans;
}

bool _edmer;
int main() {
    cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";
    int n = read();
    uniform_int_distribution <> rnd(1, 359);
    double pi = rnd(gen) / 180.0 * acos(-1.0);
    for (int i = 1; i <= n; i++) {
        int x = read(), y = read();
        edge[i].fi = x * cos(pi) - y * sin(pi),
        edge[i].se = x * sin(pi) + y * cos(pi);
    }
    sort(edge.begin() + 1, edge.begin() + 1 + n);
    printf("%.6lf\n", solve(1, n));
    return 0;
}

标签:pii,triangle,省选,double,T1,int,edge,ans,include
From: https://www.cnblogs.com/cxqghzj/p/18144533

相关文章

  • NOI 2024省选OIFC模拟21 T1(思维题)
    原我觉得非常有思维含量的一题没看懂题解,大佬讲的还是没有看懂对于一个集合S,不妨设要将这个集合设为蓝色,考虑一个包含元素最多的一个为蓝色的子集T,那么在包含有S-T集合中的元素的集合必定为红色,因为如果有一个为蓝色,那么这个与前面那个极大蓝色集合交一下就会有一个更大的蓝......
  • 无源RLC电路和阻抗匹配 part1:串并联RLC网络
    串联RLC网络回路阻抗Z(jw)=R+jwL+1/jwC;回路阻抗幅值与相角分别为当wL=1/wC时,即w=w0=1/LC,阻抗幅值达到最小值,此时回路阻抗为纯电阻R,在输入激励vi下,电流达到最大值并与vi同相,w0即为谐振频率。w<w0时,回路呈容性,阻抗相角趋近-π/2;w>w0时,回路呈感性,阻抗相角趋近π/2。品质因......
  • 2024省选OIFC模拟T1
    题意:给定k颗有n个点的树对于每个点对(i,j),求出其在每棵树上的路径经过的点(含端点)的并集大小。做法:一个比较简单的想法是搞出每个(i,j)在第k颗树上的点的集合,然后所有树并一下,这个再用bitset优化一下,然后有人就过了,而我这位大常数选手就没过。首先容斥为求不经过点的交。考......
  • web server apache tomcat11-06-Host Manager App
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目从零手写实现tomcatminicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserverapachetomcat11-02-setup启动web......
  • 洛谷题单指南-动态规划1-P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles
    原题链接:https://www.luogu.com.cn/problem/P1216题意解读:计算数字三角形最高点到最后一行路径之和最大值,典型线性DP。解题思路:设a[i][j]表示数字三角形的值,设dp[i][j]表示从最高点到第i行第j列路径之和的最大值,由于每一步可以走到左下方的点也可以到达右下方的点,所以dp[i][......
  • web server apache tomcat11-03-deploy 如何部署
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目从零手写实现tomcatminicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserverapachetomcat11-02-setup启动web......
  • web server apache tomcat11-01-官方文档入门介绍
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目同时也为从零手写实现tomcat提供一些基础和特性的思路。minicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserve......
  • P8290 [省选联考 2022] 填树
    MyBlogsP8290[省选联考2022]填树很有意思的拉插优化DP。首先可以枚举\(L\)来限制选的数的值域在\(L,L+k\)中。然后进行树上DP:设\(v_i\)表示当前点\(i\)能填多少种数,\(w_i\)表示当前点\(i\)能填的数的和。\(f_i\)表示当前\(i\)子树内的所有合法根链数量,\(g......
  • rand VS mt19937
    C++随机数randVsmt19937rand和mt19937介绍众所周知,程序无法模拟出真正的随机数,所以我们所说的随机数都是相对随机的伪随机数。rand是一种常用的随机数,C++初学者一般接触的都是他,但是他有缺点,随机性不高,周期短,质量低。Mt19937用法与rand一样但是他随机性高,周期长,质......
  • 2024/04/05 多校集训B层-省选模拟5
    T1魔法题面有\(n\)个小球排成一行,每个小球是红色或者蓝色。开始你被给定了两个非负整数\(R\)和\(B\)。每次你可以施展一个魔法,每次魔法你可以选择任意不同的\(R+B\)个球,将这些球全部变成白色,但是需要满足下列条件:你选择的\(R+B\)个球中,需要有恰好\(R\)个红球......