QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#193151 | #7521. Find the Gap | ucup-team228# | WA | 685ms | 3744kb | C++20 | 10.7kb | 2023-09-30 16:28:52 | 2023-09-30 16:28:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
std::mt19937 rnd;
typedef long double real_t;
const real_t eps = 1e-12;
template <typename T>
ostream& operator<<(ostream& ostr, const vector<T>& poly) {
for (int i = poly.size() - 1; i >= 0; i--) {
ostr << poly[i] << " x^" << i;
if (i >= 1) {
ostr << " + ";
}
}
return ostr;
}
template <typename T>
struct Rational {
T p, q;
Rational(T val) {
p = val;
q = 1;
}
Rational(T num, T den) {
p = num;
q = den;
fix();
}
Rational& fix() {
if (p == 0 || q == 0) {
p = 0;
q = 1;
}
else {
T g = __gcd(p, q);
p /= g;
q /= g;
if (q < 0) {
p = -p;
q = -q;
}
}
return *this;
}
Rational operator-() const {
return Rational(-p, q);
}
friend Rational operator+(const Rational& a, const Rational& b) {
return Rational(a.p * b.q + a.q * b.p, a.q * b.q);
}
friend Rational operator-(const Rational& a, const Rational& b) {
return Rational(a.p * b.q - a.q * b.p, a.q * b.q);
}
friend Rational operator*(const Rational& a, const Rational& b) {
return Rational(a.p * b.p, a.q * b.q);
}
friend Rational operator/(const Rational& a, const Rational& b) {
return Rational(a.p * b.q, a.q * b.p);
}
Rational& operator+=(const Rational& ot) {
return *this = *this + ot;
}
Rational& operator-=(const Rational& ot) {
return *this = *this - ot;
}
Rational& operator*=(const Rational& ot) {
return *this = *this * ot;
}
Rational& operator/=(const Rational& ot) {
return *this = *this / ot;
}
Rational& operator++(int) {
return *this += 1;
}
friend bool operator==(const Rational& a, const Rational& b) {
return a.p == b.p && a.q == b.q;
}
friend bool operator!=(const Rational& a, const Rational& b) {
return a.p != b.p || a.q != b.q;
}
friend bool operator<(const Rational& a, const Rational& b) {
return a.p * b.q < a.q * b.p;
}
friend bool operator>(const Rational& a, const Rational& b) {
return a.p * b.q > a.q * b.p;
}
operator long double() const {
return real_t(p) / real_t(q);
}
};
template <typename T>
Rational<T> abs(const Rational<T>& r) {
return {abs(r.p), abs(r.q)};
}
template <typename T = long long>
istream& operator>>(istream& istr, Rational<T>& r) {
istr >> r.p;
r.q = 1;
return istr;
}
template <typename T = long long>
ostream& operator<<(ostream& ostr, const Rational<T>& r) {
return ostr << "(" << r.p << " / " << r.q << ")";
}
template <typename T>
struct Matrix {
int row, col;
vector<vector<T>> data;
Matrix(int _row = 0, int _col = 0, bool is_identity = 0) {
row = _row;
col = _col;
data.resize(row);
for (int i = 0; i < row; i++) {
data[i].resize(col, 0);
}
if (is_identity) {
for (int i = 0; i < row; i++) {
data[i][i] = 1;
}
}
}
Matrix(vector<vector<T>> _data): data(std::move(_data)) {
row = data.size();
col = data[0].size();
}
Matrix(const vector<T>& _data) {
row = _data.size();
col = 1;
data.resize(row);
for (int i = 0; i < row; i++) {
data[i].resize(col, 0);
data[i][0] = _data[i];
}
}
vector<T>& operator[](size_t i) {
return data[i];
}
const vector<T>& operator[](size_t i) const {
return data[i];
}
Matrix transpose() const {
Matrix res(col, row);
for (int i = 0; i < res.row; i++) {
for (int j = 0; j < res.col; j++) {
res[i][j] = data[j][i];
}
}
return res;
}
Matrix operator+(const Matrix& b) const {
Matrix res(row, col);
for (int i = 0; i < res.row; i++) {
for (int j = 0; j < res.col; j++) {
res[i][j] = data[i][j] + b[i][j];
}
}
return res;
}
Matrix operator-(const Matrix& b) const {
Matrix res(row, col);
for (int i = 0; i < res.row; i++) {
for (int j = 0; j < res.col; j++) {
res[i][j] = data[i][j] - b[i][j];
}
}
return res;
}
Matrix operator*(const Matrix& b) const {
Matrix res(row, b.col);
for (int i = 0; i < res.row; i++) {
for (int j = 0; j < res.col; j++) {
for (int k = 0; k < col; k++) {
res[i][j] += data[i][k] * b[k][j];
}
}
}
return res;
}
Matrix operator+(T val) const {
Matrix res(row, col);
for (int i = 0; i < res.row; i++) {
for (int j = 0; j < res.col; j++) {
res[i][j] = data[i][j];
}
res[i][i] += val;
}
return res;
}
Matrix operator-(T val) const {
return *this + T(-val);
}
Matrix operator*(T val) const {
Matrix res(row, col);
for (int i = 0; i < res.row; i++) {
for (int j = 0; j < res.col; j++) {
res[i][j] = data[i][j] * val;
}
}
return res;
}
Matrix operator/(T val) const {
return *this * T(T(1) / val);
}
Matrix& operator+=(const Matrix& b) {
return *this = *this + b;
}
Matrix& operator-=(const Matrix& b) {
return *this = *this - b;
}
Matrix& operator*=(const Matrix& b) {
return *this = *this * b;
}
Matrix& operator+=(T val) {
return *this = *this + val;
}
Matrix& operator-=(T val) {
return *this = *this - val;
}
Matrix& operator*=(T val) {
return *this = *this * val;
}
bool operator==(const Matrix& ot) const {
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (data[i][j] != ot[i][j]) {
return 0;
}
}
}
return 1;
}
};
template <typename T>
istream& operator>>(istream& istr, Matrix<T>& a) {
for (int i = 0; i < a.row; i++) {
for (int j = 0; j < a.col; j++) {
istr >> a[i][j];
}
}
return istr;
}
template <typename T>
ostream& operator<<(ostream& ostr, const Matrix<T>& a) {
for (int i = 0; i < a.row; i++) {
if (i != 0) ostr << "\n";
for (int j = 0; j < a.col; j++) {
if (j != 0) ostr << " ";
ostr << a[i][j];
}
}
return ostr;
}
// transforms matrix A to its reduced row echelon form using Gaussian elimination and returns its determinant
template <typename T>
T Gauss(Matrix<T>& a) {
T det = 1;
for (int row = 0, col = 0; row < a.row && col < a.col; col++) {
int sel = row;
for (int i = row; i < a.row; i++) {
if (abs(a[i][col]) > abs(a[sel][col])) {
sel = i;
}
}
if (a[sel][col] == T(0)) {
continue;
}
if (sel != row) {
det *= T(-1);
}
for (int j = col; j < a.col; j++) {
swap(a[sel][j], a[row][j]);
}
for (int i = 0; i < a.row; i++) {
if (i != row) {
T c = a[i][col] / a[row][col];
for (int j = col; j < a.col; j++) {
a[i][j] -= a[row][j] * c;
}
}
}
row++;
}
for (int i = 0; i < a.row; i++) {
T val = 0;
for (int j = 0; j < a.col; j++) {
if (a[i][j] != T(0)) {
val = T(1) / a[i][j];
break;
}
}
if (val == T(0)) {
det = 0;
}
else {
det /= val;
}
for (int j = 0; j < a.col; j++) {
a[i][j] *= val;
}
}
return det;
}
struct Point {
real_t x, y, z;
Point operator+(const Point& ot) const {
return {x + ot.x, y + ot.y, z + ot.z};
}
Point operator-(const Point& ot) const {
return {x - ot.x, y - ot.y, z - ot.z};
}
};
istream& operator>>(istream& istr, Point& p) {
return istr >> p.x >> p.y >> p.z;
}
real_t dist2(Point a, Point b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z);
}
real_t dist(Point a, Point b) {
return sqrtl((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
}
real_t dot(Point a, Point b) {
return a.x * b.x + a.y * b.y + a.z * b.z;
}
real_t norm(Point a) {
return sqrtl(dot(a, a));
}
real_t volume(Point a, Point b, Point c, Point d) {
Matrix<real_t> mat(4, 4);
mat[0][0] = d.x;
mat[0][1] = d.y;
mat[0][2] = d.z;
mat[1][0] = a.x;
mat[1][1] = a.y;
mat[1][2] = a.z;
mat[2][0] = b.x;
mat[2][1] = b.y;
mat[2][2] = b.z;
mat[3][0] = c.x;
mat[3][1] = c.y;
mat[3][2] = c.z;
mat[0][3] = mat[1][3] = mat[2][3] = mat[3][3] = 1;
return Gauss(mat);
}
real_t area(Point a, Point b, Point c) {
Point ab = b - a;
Point ac = c - a;
real_t ang = acos(dot(ab, ac) / norm(ab) / norm(ac));
return norm(ab) * norm(ac) * sin(ang) / 2;
}
const int N = 50 + 10;
Point a[N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
cout << fixed << setprecision(12);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
real_t ans = 1e18;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
for (int k = j + 1; k <= n; k++) {
real_t mn = 0, mx = 0;
for (int t = 1; t <= n; t++) {
real_t cur = volume(a[i], a[j], a[k], a[t]) / area(a[i], a[j], a[k]) / 2;
mn = min(mn, cur);
mx = max(mx, cur);
}
if (mn > -eps) {
ans = min(ans, mx);
}
if (mx < eps) {
ans = min(ans, -mn);
}
}
}
}
cout << ans << "\n";
#ifdef LOCAL
cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3744kb
input:
8 1 1 1 1 1 2 1 2 1 1 2 2 2 1 1 2 1 2 2 2 1 2 2 2
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
5 1 1 1 1 2 1 1 1 2 1 2 2 2 1 1
output:
0.707106781187
result:
ok found '0.707106781', expected '0.707106781', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 685ms
memory: 3652kb
input:
50 973 1799 4431 1036 1888 4509 1099 1977 4587 1162 2066 4665 1225 2155 4743 1288 2244 4821 1351 2333 4899 1414 2422 4977 1540 2600 5133 1603 2689 5211 1666 2778 5289 1729 2867 5367 1792 2956 5445 1855 3045 5523 1918 3134 5601 1981 3223 5679 2044 3312 5757 2107 3401 5835 2170 3490 5913 2296 3668 606...
output:
1000000000000000000.000000000000
result:
wrong answer 1st numbers differ - expected: '0.0000000', found: '1000000000000000000.0000000', error = '1000000000000000000.0000000'