QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#723672 | #9520. Concave Hull | nan01 | RE | 1ms | 3836kb | C++23 | 14.5kb | 2024-11-07 23:34:50 | 2024-11-07 23:34:51 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define ll long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#define fi first
#define pll pair<ll, ll>
#define se second
#define lll __int128
#define ld long double
#define all(a) a.begin() + 1, a.end()
#define iofast \
ios::sync_with_stdio(false); \
cin.tie(0), cout.tie(0)
#define lowbit(i) (i & (-i))
using namespace std;
const int maxn = 1e6 + 5, mod = 1000000007;
// 三角形重心是 (x1+ x2+x3)/3, (y1+y2 + y3)/3
// if 外心= (0,0)
// -> 垂心=(x1+x2+x3, y1+y2+y3) (欧拉线:重心,外心,垂心共线,2*dis(外心,重心)=dis(重心,垂心)
// 内心=角平分线交点,角平分线与外接圆的三个交点组成的三角形的垂心等于原三角形的内心
const double eps = 1e-10;
int sgn(double a)
{
if (fabs(a) < eps)
return 0;
if (a < 0)
return -1;
return 1;
}
template <class T>
class point
{
public:
T x, y;
point(T a, T b) : x(a), y(b) {}
point() {};
point operator+(point a) { return point(x + a.x, y + a.y); }
point operator-(point a) { return point(x - a.x, y - a.y); }
point operator*(double a) { return point(x * a, y * a); }
point operator/(double a) { return point(x / a, y / a); }
T operator*(point a) { return x * a.x + y * a.y; }
T operator%(point a) { return x * a.y - y * a.x; }
bool operator==(point a) { return x == a.x && y == a.y; }
friend istream &operator>>(istream &is, point<T> &x)
{
is >> x.x >> x.y;
return is;
}
friend ostream &operator<<(ostream &os, const point<T> &x) { return os << x.x << " " << x.y; }
};
template <class T>
struct circle
{
point<T> o;
T r;
};
template <class T>
class line
{
public:
point<T> s, t;
};
template <typename T>
T mul(point<T> a, point<T> b, point<T> c) // c和ab叉乘 当ca逆时针转小于180度遇到cb时为正
{
return (c - a) % (c - b);
}
template <typename T>
T dot(point<T> a, point<T> b, point<T> c) // ab和ac点乘
{
return (a - b) * (a - c);
}
template <typename T>
point<T> interpoint(point<T> s1, point<T> t1, point<T> s2, point<T> t2) // 向量交点
{
auto t = fabs(((t2 - s2) % (s2 - s1)) / ((t2 - s2) % (t1 - s1)));
return s1 + (t1 - s1) * fabs(((t2 - s2) % (s2 - s1)) / ((t2 - s2) % (t1 - s1)));
}
template <typename T>
point<T> cross(point<T> a, point<T> b, point<T> c, point<T> d) // 直线交点
{
auto v = c - d;
ld sa = v % (a - d), sb = (b - d) % v;
ld rate = sa / (sa + sb);
return (b - a) * rate + a;
}
template <typename T>
inline bool parallel(point<T> s1, point<T> t1, point<T> s2, point<T> t2) // 判断平行 最好用整数point,别用double
{
return ((t1 - s1) % (t2 - s2)) == 0;
}
template <typename T>
inline bool isinseg(point<T> s, point<T> t, point<T> mid) // 判断mid是否在st线段内,double改成eps
{
return dot(mid, s, t) <= 0;
}
template <typename T>
double dis(point<T> a, point<T> b) // ab距离
{
return sqrt((a - b) * (a - b));
}
template <typename T>
T distoline(point<T> a, point<T> b, point<T> c) // c到ab直线距离
{
auto u = a - b, v = a - c;
return fabs(u % v / dis(a, b));
}
template <typename T>
T distoseg(point<T> a, point<T> b, point<T> c) // c到ab线段距离
{
auto u = b - a, v = c - a, w = c - b;
if (a == b)
return dis(c, b);
if (u * v < 0)
return dis(c, a);
if (u * w > 0)
return dis(b, c);
return distoline(a, b, c);
}
template <typename T>
T sqadis(point<T> a, point<T> b) // ab平方距离
{
return (a - b) * (a - b);
}
template <typename T>
bool cmp(point<T> a, point<T> b) // x第一关键字,y第二关键字
{
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
template <typename T>
point<T> rot(point<T> a) // 逆时针旋转90
{
return point{-a.y, a.x};
}
template <typename T>
point<T> rotate(point<T> a, double angle) // 顺时针旋转angle度
{
return point{a.x * cos(angle) + a.y * sin(angle), -a.x * sin(angle) + a.y * cos(angle)};
}
template <typename T>
double angle(point<T> a, point<T> b, point<T> c) // 返回b-a和c-a的tan值 垂直则返回-1;
{
auto v1 = b - a;
auto v2 = c - a;
if (v1 * v2 == 0)
return -1;
return double(v1 % v2) / (v1 * v2);
}
template <typename T>
point<T> excir(point<T> a, point<T> b, point<T> c) // 求外接圆圆心
{
auto d1 = (a + b) * 0.5, d2 = d1 + rot(a - b);
auto d3 = (c + b) * 0.5, d4 = d3 + rot(c - b);
return cross(d1, d2, d3, d4);
}
template <typename T>
bool check(circle<T> a, point<T> b) // 判断点是否在圆外
{
if (dis(a.o, b) - a.r > eps)
return false;
else
return 1;
}
template <typename T>
circle<T> smallestcircle(vector<point<T>> a) // 最小覆盖圆
{
int n = a.size() - 1;
random_shuffle(a.begin() + 1, a.begin() + n + 1);
circle<T> c{a[1], 0};
rep(i, 2, n)
{
if (!check(c, a[i]))
{
c = circle<T>{a[i], 0};
rep(j, 1, i - 1)
{
if (!check(c, a[j]))
{
c = circle<T>{(a[i] + a[j]) * 0.5, dis(a[i], a[j]) / 2.0};
rep(k, 1, j - 1)
{
if (!check(c, a[k]))
{
point<double> o = excir(a[i], a[j], a[k]);
c = circle<T>{o, dis(o, a[i])};
}
}
}
}
}
}
return c;
}
template <typename T>
bool isinter(point<T> a, point<T> b, point<T> c, point<T> d) // 两线段是否相交
{
double c1 = (c - a) % (b - a), c2 = (d - a) % (b - a);
double c3 = (b - d) % (c - d), c4 = (a - d) % (c - d);
return sgn(c1) * sgn(c2) < 0 && sgn(c3) * sgn(c4) < 0;
}
template <typename T>
vector<point<T>> graham(vector<point<T>> p, bool flag = 1) // 求凸包 1-index
{
sort(all(p), cmp<T>);
int n = p.size() - 1;
vector<point<T>> h(n + 2);
h[1] = p[1];
int m = 1;
rep(i, 2, n)
{
while (m > 1 && mul(h[m - 1], h[m], p[i]) <= 0)
m--;
h[++m] = p[i];
}
int k = m;
for (int i = n - 1; i >= 1; i--)
{
while (m > k && mul(h[m - 1], h[m], p[i]) <= 0)
m--;
h[++m] = p[i];
}
h.resize(m + flag); // flag=1 不删除最后一个点 反之删除 最后一个点也是第一个点
return h;
}
template <typename T>
bool ispointinhull(vector<point<T>> p, point<T> a) // log判断点是否再凸包内
{
int n = p.size() - 1;
int l = 0, r = n;
while (l < r - 1)
{
int mid = l + r >> 1;
T x = mul(p[mid], a, p[0]);
T y = mul(p[mid + 1], a, p[0]);
if (sgn(x) >= 0 && sgn(y) <= 0)
{
if (sgn(mul(p[mid + 1], a, p[mid])) >= 0)
{
return 1;
}
return 0;
}
else if (sgn(y) > 0)
l = mid;
else
r = mid;
}
return 0;
}
template <typename T>
double zuijindiandui(vector<point<T>> a) // 最近公共点对
{
sort(all(a), cmp<T>);
double mn = 2e18;
int n = a.size() - 1;
auto cal = [&](auto self, int l, int r) -> void
{
if (l == r)
return;
int m = l + r >> 1;
self(self, l, m);
self(self, m + 1, r);
double mid = (a[m].x + a[m + 1].x) / 2;
int L = m;
while (L >= l && a[L].x >= mid - mn)
{
L--;
}
L++;
int R = m + 1;
while (R <= r && a[R].x <= mid + mn)
R++;
R--;
rep(i, L, m)
{
rep(j, m + 1, R)
{
mn = min(mn, dis(a[i], a[j]));
}
}
};
cal(cal, 1, n);
return mn;
}
template <typename T>
T xzkk(vector<point<T>> a) // 旋转卡壳
{
a = graham(a, 0); // 要删掉最后一个点!
T mx = 0;
int j = 3;
int n = a.size() - 1;
if (n == 2) // 如果是直线
{
return dis(a[1], a[2]);
}
a.push_back(a[1]);
rep(i, 1, n)
{
mx = max(mx, dis(a[i], a[i + 1]));
while (llabs(mul(a[i], a[i + 1], a[j])) <= llabs(mul(a[i], a[i + 1], a[j + 1])))
j = (j % n) + 1;
mx = max(mx, max(dis(a[i], a[j]), dis(a[i + 1], a[j])));
}
return mx;
}
template <typename T>
double angle(line<T> a) // 直线的极角
{
return atan2(a.t.y - a.s.y, a.t.x - a.s.x);
}
template <typename T>
inline point<T> cross(line<T> a, line<T> b) // 两直线交点
{
return cross(a.s, a.t, b.s, b.t);
}
template <typename T>
bool right(line<T> a, line<T> b, line<T> c) // bc交点时候在a右边
{
auto d = cross(b, c);
return mul(a.s, a.t, d) < 0; // 在线上不算
}
template <typename T>
bool left(line<T> a, line<T> b, line<T> c) // bc交点时候在a右边
{
auto d = cross(b, c);
return mul(a.s, a.t, d) >= 0; // 在线上算
}
template <typename T>
vector<point<T>> halfplane(vector<line<T>> a) // 半平面交
{
sort(all(a), [&](auto a, auto b)
{ double x = angle(a), y = angle(b);
return fabs(x-y) > eps ? x<y : mul(b.s, b.t, a.t) > 0; });
deque<line<T>> q;
q.push_back(a[1]);
rep(i, 2, (int)a.size() - 1)
{
if (fabs(angle(a[i]) - angle(q.back()) < eps))
continue;
while (q.size() > 1)
{
auto t = q.back();
q.pop_back();
if (left(a[i], t, q.back()))
{
q.push_back(t);
break;
}
}
while (q.size() > 1)
{
auto t = q.front();
q.pop_front();
if (left(a[i], t, q.front()))
{
q.push_front(t);
break;
}
}
q.push_back(a[i]);
}
while (q.size() > 2)
{
auto t = q.back();
q.pop_back();
if (left(q.front(), t, q.back()))
{
q.push_back(t);
break;
}
}
int siz = q.size();
q.push_back(q.front());
vector<point<T>> ret(1); // 1-index
rep(i, 1, siz)
{
auto t = q.front();
q.pop_front();
ret.push_back(cross(t, q.front()));
}
return ret;
}
template <typename T>
ll area(vector<point<T>> a) // 一个凸包求面积
{
int siz = a.size() - 1;
ll ret = 0;
rep(i, 2, siz - 1)
{
ret += mul(a[1], a[i], a[i + 1]);
}
return ret;
}
template <typename T>
struct matrix
{
point<T> a, b, c, d;
T area;
matrix(point<T> a, point<T> b, point<T> c, point<T> d, T area = 0) : a(a), b(b), c(c), d(d), area(area) {}
matrix() : area(0) {}
};
template <typename T>
matrix<T> minmatcover(vector<point<T>> p) // p为1-index 最小矩形覆盖 (最小正方形覆盖三分)
{
p = graham(p);
int n = (int)p.size() - 2;
p[0] = p[n];
// j右边 k上边 h左边
double ret = 2e18;
array<int, 4> ansi;
for (int i = 1, j = 1, k = 2, h = -1; i <= n; i++)
{
// cout << p[i].x << " " << p[i].y << endl;
auto cur = p[i + 1] - p[i];
while ((p[j + 1] - p[i]) * (cur)-eps > (p[j] - p[i]) * (cur))
{
j = (j % n) + 1;
}
while (mul(p[i + 1], p[k], p[i]) < mul(p[i + 1], p[k + 1], p[i]) - eps)
{
k = (k % n) + 1;
}
if (h == -1)
h = k;
while ((p[h + 1] - p[i]) * (cur) < (p[h] - p[i]) * (cur)-eps)
{
h = (h % n) + 1;
}
// cout << j << " " << k << " " << h << endl;
double len = ((p[j] - p[i]) * (cur) - (p[h] - p[i]) * (cur)) / dis(p[i], p[i + 1]);
double wid = distoline(p[i], p[i + 1], p[k]);
// cout << len * wid << "\n";
if (ret > len * wid)
{
ret = len * wid;
ansi = array{i, j, k, h};
}
}
matrix<T> res;
{
auto [i, j, k, h] = ansi;
auto t = (p[i + 1] - p[i]) / dis(p[i + 1], p[i]); // 矩形一条边的单位向量
auto x = t * (t * (p[j] - p[i])); // 最右边的点的在该单位向量上的影射
auto y = rot(t) * distoline(p[i], p[i + 1], p[k]); // 矩形的宽的向量
auto z = t * (t * (p[h] - p[i])); // 最左边的点的在该单位向量上的影射
res.a = (x + p[i]);
res.b = (x + y + p[i]);
res.c = (z + y + p[i]);
res.d = (z + p[i]);
res.area = ret;
}
return res; // 按照逆时针排序矩形四个点
}
void solve()
{
int n;
cin >> n;
vector<point<ll>> a(n + 1);
rep(i, 1, n)
{
cin >> a[i];
}
auto h = graham(a);
vector<int> cnt(n + 1);
sort(all(a), cmp<ll>);
vector<point<ll>> b(1);
int j = 1;
for (int i = 1; i <= n; i++)
{
if (a[i] == h[j])
{
j++;
continue;
}
cnt[i]++;
// b.push_back(a[i]);
}
for (int i = n; i > 0; i--)
{
if (a[i] == h[j])
{
j++;
continue;
}
cnt[i]++;
}
for (int i = 1; i <= n; i++)
{
if (cnt[i] == 2)
{
b.push_back(a[i]);
}
}
if (b.size() == 1)
{
cout << -1 << endl;
return;
}
auto h2 = graham(b, 0);
j = 1;
n = h.size() - 2;
int m = h2.size() - 1;
// cout << n << m << endl;
auto nxt = [&](int x)
{
return x % n + 1;
};
auto ret = area(h);
ll mn = 2e18;
for (int i = 1; i <= n; i++)
{
while (llabs(mul(h[i], h[nxt(i)], h2[j])) >= llabs(mul(h[i], h[nxt(i)], h2[j % m + 1])))
{
j = j % m + 1;
}
mn = min(mn, llabs(mul(h[i], h[nxt(i)], h2[j])));
}
// for (int i = 1; i < h2.size(); i++)
// {
// while (mul(h[j], h[nxt(j)], h2[i]) >= mul(h[nxt(j)], h[nxt(nxt(j))], h2[i]))
// {
// j = nxt(j);
// }
// mn = min(mn, mul(h[j], h[nxt(j)], h2[i]));
// }
assert(mn >= 0);
cout << ret - mn << endl;
}
int main()
{
iofast;
int t = 1;
cin >> t;
while (t--)
solve();
// cout << endl;
// system("pause");
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3836kb
input:
2 6 -2 0 1 -2 5 2 0 4 1 2 3 1 4 0 0 1 0 0 1 1 1
output:
40 -1
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
10 243 -494423502 -591557038 -493438474 -648991734 -493289308 -656152126 -491185085 -661710614 -489063449 -666925265 -464265894 -709944049 -447472922 -737242534 -415977509 -773788538 -394263365 -797285016 -382728841 -807396819 -373481975 -814685302 -368242265 -818267002 -344482838 -833805545 -279398...
output:
2178418010787347715 1826413114144932145 1651687576234220014 1883871859778998985 2119126281997959892 894016174881844630 2271191316922158910 1998643358049669416 1740474221286618711 1168195646932543192
result:
ok 10 lines
Test #3:
score: -100
Runtime Error
input:
1000 125 64661186 -13143076 302828013 -185438065 -418713797 -191594241 430218126 -397441626 354327250 -836704374 149668812 -598584998 311305970 66790541 199720625 -592356787 468137 -584752683 258775829 96211747 -358669612 -134890109 -129221188 -998432368 -277309896 -140056561 356901185 420557649 -51...
output:
1986320445246155278 1900093336073022078 1612088392301142476 2012259136539173407 1819942017252118749 1772230185841892196 1164835025329039520 1527446155241140517 1807368432185303666 1236918659444944569 1306839249967484778 1984123720246784099 1868728080720036006 667458140583450322 2127932992585026491