QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#316157 | #784. 旋转卡壳 | lmf_up | 0 | 1ms | 3936kb | C++20 | 11.5kb | 2024-01-27 17:49:34 | 2024-05-30 09:01:11 |
Judging History
你现在查看的是最新测评结果
- [2024-10-16 12:18:36]
- hack成功,自动添加数据
- (/hack/1005)
- [2024-09-24 16:55:39]
- hack成功,自动添加数据
- (/hack/888)
- [2024-07-31 21:52:32]
- hack成功,自动添加数据
- (/hack/764)
- [2024-07-31 21:47:53]
- hack成功,自动添加数据
- (/hack/763)
- [2024-05-30 09:00:15]
- hack成功,自动添加数据
- (/hack/642)
- [2024-01-27 17:49:34]
- 提交
answer
#include<bits/stdc++.h>
#define cp const point &
#define cl const line &
#define cc const circle &
#define LD long double
std::mt19937 rnd(time(0));
const LD eps = 1e-8;
const LD pi = std::numbers::pi;
const LD INF = 1e9;
int sgn(LD x)
{
return x > eps ? 1 : (x < -eps ? -1 : 0);
}
LD sqr(LD x)
{ return x * x; }
struct point
{
LD x, y;
point operator+(cp a) const
{ return {x + a.x, y + a.y}; }
point operator-(cp a) const
{ return {x - a.x, y - a.y}; }
point operator*(LD t) const
{ return {x * t, y * t}; }
point operator/(LD t) const
{ return {x / t, y / t}; }
point rot(LD t) const
{ return {x * cos(t) - y * sin(t), x * sin(t) + y * cos(t)}; }
point rot90() const
{ return {-y, x}; }
LD len2() const
{ return x * x + y * y; }
LD len() const
{ return sqrtl(x * x + y * y); }
point unit() const
{
double d = len();
return {x / d, y / d};
}
friend bool operator<(cp a, cp b)
{
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
friend bool operator>(cp a, cp b)
{
return a.x == b.x ? a.y > b.y : a.x > b.x;
}
};
LD dot(cp a, cp b);
bool operator==(cp a, cp b)
{
return !sgn(dot(a - b, a - b));
}
LD dis(cp a, cp b)//两点距离
{
return sqrtl(sqr(a.x - b.x) + sqr(a.y - b.y));
}
LD dot(cp a, cp b)//点乘
{
return a.x * b.x + a.y * b.y;
}
LD det(cp a, cp b)//叉乘
{
return a.x * b.y - b.x * a.y;
}
bool turn_left(cp a, cp b, cp c)//判断ba是否逆时针转少于180°到ca
{
return sgn(det(b - a, c - a)) > 0;//大于是严格凸包
}
struct line
{
point s, t;
line(point a, point b) : s(a), t(b)
{}
};
struct circle
{
point c;
LD r;
circle()
{}
circle(point C, LD R)
{ c = C, r = R; }
};
bool in_circle(cp a, cc b)
{
return sgn((b.c - a).len() - b.r) <= 0;
}
circle make_circle(point u, point v)
{
point p = (u + v) / 2;
return circle(p, (u - p).len());
}
circle make_circle(cp a, cp b, cp c)
{
point p = b - a, q = c - a;
point s(dot(p, p) / 2, dot(q, q) / 2);
LD d = det(p, q);
p = point(det(s, point(p.y, q.y)), det(point(p.x, q.x), s)) / d;
return circle(a + p, p.len());
}
circle min_circle(std::vector<point> p)
{
circle ret(p[0], 0);
std::shuffle(p.begin(), p.end(), rnd);
int len = p.size();
for (int i = 0; i < len; i++)
if (!in_circle(p[i], ret))
{
ret = circle(p[i], 0);
for (int j = 0; j < i; j++)
if (!in_circle(p[j], ret))
{
ret = make_circle(p[j], p[i]);
for (int k = 0; k < j; ++k)
if (!in_circle(p[k], ret))
ret = make_circle(p[i], p[j], p[k]);
}
}
return ret;
}
bool same_dir(cl a, cl b)//判断方向是否一致
{
return sgn(det(b.t - b.s, a.t - a.s)) == 0 && sgn(dot(b.t - b.s, a.t - a.s)) > 0;
}
bool point_on_line(cp a, cl l)//判断点是否在直线上
{
return sgn(det(a-l.s, l.t - l.s)) == 0;
}
bool point_on_segment(cp a, cl l)//判断点是否在线段上
{
return point_on_line(a, l) && sgn(dot(l.s - a, l.t-a )) <= 0;
}
bool two_side(cp a, cp b, cl c)//判断两个点是否在线段的两边
{
return sgn(det(a - c.s, c.t - c.s)) * sgn(det(b - c.s, c.t - c.s)) < 0;
}
bool intersect_judge(cl a, cl b)
{//判断两个线段是否相交
if (point_on_segment(a.s, b) || point_on_segment(a.t, b) || point_on_segment(b.s, a) ||
point_on_segment(b.t, a))
return true;
return two_side(a.s, a.t, b) && two_side(b.s, b.t, a);
}
point line_intersect(cl a, cl b)
{//得到两线段的交点
double s1 = det(a.t - a.s, b.s - a.s);
double s2 = det(a.t - a.s, b.t - a.s);
return (b.s * s2 - b.t * s1) / (s2 - s1);
}
bool point_on_ray(cp a, cl b)
{//判断点是否在射线上
return sgn(det(a - b.s, b.t - b.s)) == 0 && sgn(dot(a - b.s, b.t - b.s)) >= 0;
}
bool ray_intersect_judge(line a, line b)//判断两射线是否相交
{
double s1, s2;
s1 = det(a.t - a.s, b.s - a.s);
s2 = det(a.t - a.s, b.t - a.s);
if (sgn(s1) == 0 && sgn(s2) == 0)
return sgn(dot(a.t - a.s, b.s - a.s)) >= 0 || sgn(dot(b.t - b.s, a.s - b.s));
if (!sgn(s1 - s2) || sgn(s1) == sgn(s2 - s1))return 0;
std::swap(a, b);
s1 = det(a.t - a.s, b.s - a.s);
s2 = det(a.t - a.s, b.t - a.s);
return sgn(s1) != sgn(s2 - s1);
}
LD point_to_line(cp a, cl b)
{//点到直线的距离
return abs(det(b.t - b.s, a - b.s)) / dis(b.s, b.t);
}
point project_to_line(cp a, cl b)
{//得到点在线上的投影
return b.s + (b.t - b.s) * (dot(a - b.s, b.t - b.s) / (b.t - b.s).len2());
}
LD point_to_segment(cp a, cl b)
{//点到线段的距离
if (b.s == b.t)
return dis(a, b.s);
if (sgn(dot(b.s - a, b.t - b.s)) * sgn(dot(b.t - a, b.t - b.s)) <= 0)
return abs(det(b.t - b.s, a - b.s)) / dis(b.s, b.t);
return std::min(dis(a, b.s), dis(a, b.t));
}
std::vector<point> convex_hull(std::vector<point> a)
{//凸包,字典序
int n = (int) a.size(), cnt = 0;
if (n < 2) return a;
std::sort(a.begin(), a.end()); // less<pair>
std::vector<point> ret;
for (int i = 0; i < n; ++i)
{
while (cnt > 1
&& !turn_left(ret[cnt - 1], a[i], ret[cnt - 2]))
--cnt, ret.pop_back();
++cnt, ret.push_back(a[i]);
}
int fixed = cnt;
for (int i = n - 2; i >= 0; --i)
{
while (cnt > fixed
&& !turn_left(ret[cnt - 1], a[i], ret[cnt - 2]))
--cnt, ret.pop_back();
++cnt, ret.push_back(a[i]);
}
ret.pop_back();
return ret;
}
std::vector<point> minkovski(std::vector<std::vector<point>> a)
{
if (a[0].size() == 1)
return a[1];
if (a[1].size() == 1)
return a[0];
for (int i = 0; i < 2; i++)a[i].push_back(a[i].front());
int i[2] = {0, 0}, len[2] = {(int) a[0].size() - 1, (int) a[1].size() - 1};
std::vector<point> ret;
ret.push_back(a[0][0] + a[1][0]);
do
{
int d = sgn(det(a[1][i[1] + 1] - a[1][i[1]], a[0][i[0] + 1] - a[0][i[0]])) >= 0;
ret.push_back(a[d][i[d] + 1] - a[d][i[d]] + ret.back());
i[d] = (i[d] + 1) % len[d];
}
while (i[0] || i[1]);
return ret;
}
struct Convex
{
int n;
std::vector<point> a, upper, lower;
Convex(std::vector<point> _a) : a(_a)
{
n = a.size();
int k = 0;
for (int i = 1; i < n; i++)if (a[k] < a[i])k = i;
for (int i = 0; i <= k; i++) lower.push_back(a[i]);
for (int i = k; i < n; i++) upper.push_back(a[i]);
upper.push_back(a[0]);
}
std::pair<LD, int> get_tan(std::vector<point> &con, point vec)
{
int l = 0, r = (int) con.size() - 2;
for (; l + 1 < r;)
{
int mid = (l + r) / 2;
if (sgn(det(con[mid + 1] - con[mid], vec)) > 0)r = mid;
else l = mid;
}
return std::max(std::make_pair(det(vec, con[r]), r), std::make_pair(det(vec, con[0]), 0));
}
void upd_tan(cp p, int id, int &i0, int &i1)
{
if (sgn(det(a[i0] - p, a[id] - p)) > 0) i0 = id;
if (sgn(det(a[i1] - p, a[id] - p)) < 0) i1 = id;
}
void search(int l, int r, point p, int &i0, int &i1)
{
if (l == r)return;
upd_tan(p, l % n, i0, i1);
int sl = sgn(det(a[l % n] - p, a[(l + 1) % n] - p));
for (; l + 1 < r;)
{
int mid = (l + r) / 2;
int smid = sgn(det(a[mid % n] - p, a[(mid + 1) % n] - p));
if (smid == sl)l = mid;
else r = mid;
}
upd_tan(p, r % n, i0, i1);
}
int search(point u, point v, int l, int r)
{
int sl = sgn(det(v - u, a[l % n] - u));
for (; l + 1 < r;)
{
int mid = (l + r) / 2;
int smid = sgn(det(v - u, a[mid % n] - u));
if (smid == sl) l = mid;
else r = mid;
}
return l % n;
}
//判定点是否在凸包内,在边界返回true
bool contain(point p)
{
if (p.x < lower[0].x || p.x > lower.back().x)return false;
int id = std::lower_bound(lower.begin(), lower.end(), point(p.x, -INF)) - lower.begin();
if (lower[id].x == p.x)
{
if (lower[id].y > p.y)return false;
}
else if (det(lower[id - 1] - p, lower[id] - p) < 0)
return false;
id = std::lower_bound(upper.begin(), upper.end(), point(p.x, INF), std::greater<point>()) - upper.begin();
if (upper[id].x == p.x)
{
if (upper[id].y < p.y)return false;
}
else if (det(upper[id - 1] - p, upper[id] - p) < 0)
return false;
return true;
}
};
std::vector<point> Minkovski(std::vector<std::vector<point>> a)
{ //闵可夫斯基和
std::vector<point> S;
int n = a[0].size(), m = a[1].size();
std::vector<point> A(n ), B(m );
for (int i = 0; i < n - 1; i++) A[i] = a[0][i + 1] - a[0][i];
A[n - 1] = a[0][0] - a[0][n - 1];
for (int i = 0; i < m - 1; i++) B[i] = a[1][i + 1] - a[1][i];
B[m - 1] = a[1][0] - a[1][m - 1]; //将两个凸包上的边向量都存入a,b中
S.push_back(a[0][0] + a[1][0]);
int p1 = 0, p2 = 0;
while (p1 < n && p2 < m)
{
LD d = det(A[p1], B[p2]);
if (d > 0)
S.push_back(S.back()+A[p1++]);
else if (d < 0)
S.push_back(S.back()+B[p2++]);
else
{
if(dot(A[p1],B[p1])>=0)
S.push_back(S.back()+A[p1++]);
else
{
auto [x,y]=A[p1];
if(x>0)
S.push_back(S.back()+A[p1++]);
else if(x<0)
S.push_back(S.back()+B[p2++]);
else
{
if(y>0)
S.push_back(S.back()+A[p1++]);
else S.push_back(S.back()+B[p2++]);
}
}
}
}
while (p1 < n)
S.push_back(S.back() + A[p1++]);
while (p2 < m)
S.push_back(S.back() + B[p2++]);
return S;
}
void print(std::vector<point> res)
{
std::cout << "print:\n";
for (auto [x, y]: res)
std::cout << x << ' ' << y << std::endl;
std::cout << "end\n";
}
void solve()
{
int n;
std::cin>>n;
std::vector<point>pu(n);
for(int i=0;i<n;i++)
std::cin>>pu[i].x>>pu[i].y;
int it=2;
LD ans=0;
for(int i=0;i<n;i++)
{
while(abs(det(pu[it]-pu[i],pu[(i+1)%n]-pu[i]))<abs(det(pu[(it+1)%n]-pu[i],pu[(i+1)%n]-pu[i])))
it=(it+1)%n;
ans=std::max(ans,std::max(dis(pu[it],pu[i]),dis(pu[it],pu[(i+1)%n])));
}
std::cout<<ans<<std::endl;
}
void test()
{
// point a(1,1),b(2,2);
// if(point_on_segment(a,line(b,b)))std::cout<<1<<std::endl;
// exit(0);
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
std::cout << std::fixed << std::setprecision(10);
int T = 1;
test();
// std::cin>>T;
while (T--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3936kb
input:
1000 0 0 -997615 -8573 -1988394 -28911 -2726572 -44296 -3491635 -60392 -4419752 -82814 -5298550 -105946 -5723430 -118453 -6608257 -147267 -7034966 -161982 -7563964 -181682 -8507871 -222865 -9499799 -271846 -10090186 -303547 -10400262 -322989 -10614073 -339725 -11081438 -378596 -11791568 -439127 -127...
output:
274220266.4669370932
result:
wrong answer 1st numbers differ - expected: '274339223.1895614', found: '274220266.4669371', error = '0.0004336'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%