QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#245022 | #2827. Autobiography | Delay_for_five_minutes# | WA | 1ms | 3660kb | C++11 | 4.9kb | 2023-11-09 17:55:12 | 2023-11-09 17:55:13 |
Judging History
answer
#include<bits/stdc++.h>
#define y1 yyyy
int x1,y1,z1,x2,y2,z2;
int x3,y3,z3,x4,y4,z4;
bool ZERO(int &a,int &b,int &c,int &d) {
// a = 0;
b -= a;
c -= a;
d -= a;
if (b < 0) {
b = -b,c = -c;d = -d;
}
if (c > d) {
std::swap(c,d);
}
if (c < 0) {
c = 0;
}
if (c > b) {
c = b;
}
if (d < 0) {
d = 0;
}
if (d > b) {
d = b;
}
// printf("%d %d %d %d\n",a,b,c,d);
if (c == d) return 1;
return 0;
}
struct vec {
double x,y,z;
vec operator - (const vec &B) const {
return (vec){x - B.x,y - B.y, z - B.z};
}
vec operator * (const vec &B) const {
return (vec){y * B.z - z * B.y, z * B.x - x * B.z, x * B.y - y * B.x};
}
double len() {
return sqrt(x * x + y * y + z * z);
}
};
std::vector<vec> con;
double dot(vec A,vec B) {
return A.x * B.x + A.y * B.y + A.z * B.z;
}
struct pln {
int v[3];
vec norm() {
return (con[v[1]] - con[v[0]]) * (con[v[2]] - con[v[0]]);
}
double area() {
return norm().len()*0.5;
}
double V() {
return dot(norm(),con[v[0]])/6;
}
bool out(int x) {
return dot(con[x] - con[v[0]],norm()) > 0;
}
};
bool check(double x,double y,double z) {
return x / x2 + y / y2 + z / z2 - 1 < 0;
}
void Push(double x,double y,double z) {
if (check(x,y,z)) {
con.push_back({x,y,z});
}
}
vec get(std::vector<int> v, int R,int pos) {
double l = v[pos], r = R;
std::vector<double> v1;v1.resize(3);
v1[0] = v[0],v1[1] = v[1],v1[2] = v[2];
for(int i = 1; i <= 60; i++) {
double mid = l + (r - l)/2;
v1[pos] = mid;
if (check(v1[0],v1[1],v1[2])) {
l = mid;
}
else {
r = mid;
}
}
return (vec){v1[0],v1[1],v1[2]};
}
double eps = 1e-9;
double rd() {
return (rand() / RAND_MAX - 1) * eps;
}
double getV() {
int mk[40][40];
memset(mk,0,sizeof mk);
for(int i = 0; i < con.size(); i++) {
con[i].x += rd();
con[i].y += rd();
con[i].z += rd();
}
int m = 0,c;
pln b[40],o[40];
b[++m] = (pln){0,1,2};
b[++m] = (pln){2,1,0};
for(int i = 3; i < con.size(); i ++) {
c = 0;
for(int j = 1; j <= m ;j++) {
int vis = b[j].out(i);
if (!vis) o[++c] = b[j];
for(int k = 0; k < 3; k++) {
mk[b[j].v[k]][b[j].v[(k+1)%3]]=vis;
}
}
for(int j = 1; j <= m; j++) {
for(int k = 0; k < 3; k++) {
int x = b[j].v[k],y = b[j].v[(k + 1) % 3];
if (mk[x][y]&&!mk[y][x]) {
o[++c] = (pln){x,y,i};
}
}
}
for(int j = 1; j <= c; j++)
b[j] = o[j];
m = c;
}
double ans = 0;
// printf("%d\n",m);
bool vis[40];
memset(vis,0,sizeof vis);
for(int i = 1; i <= m; i++) {
vis[b[i].v[0]] = vis[b[i].v[1]] = vis[b[i].v[2]] = 1;
ans += b[i].V();
}
for(int i = 0; i < con.size(); i++) if (vis[i]){
printf("%lf %lf %lf\n",con[i].x,con[i].y,con[i].z);
}
return ans;
}
void solve() {
std::cin >> x2 >> y2 >> z2;
std::cin >> x3 >> y3 >> z3;
std::cin >> x4 >> y4 >> z4;
if (ZERO(x1,x2,x3,x4) || ZERO(y1,y2,y3,y4) || ZERO(z1,z2,z3,z4)) {
std::cout << 2333 << std::endl;
return ;
}
con.clear();
Push(x3,y3,z3);
Push(x3,y3,z4);
Push(x3,y4,z3);
Push(x3,y4,z4);
Push(x4,y3,z3);
Push(x4,y3,z4);
Push(x4,y4,z3);
Push(x4,y4,z4);
// for(auto i : con) {
// printf("%lf %lf %lf\n",i.x,i.y,i.z);
// }
if (check(x3,y3,z3) != check(x3,y3,z4)) {
con.push_back(get(std::vector<int>({x3,y3,z3}),z4,2));
}
if (check(x3,y3,z3) != check(x3,y4,z3)) {
con.push_back(get(std::vector<int>({x3,y3,z3}),y4,1));
}
if (check(x3,y3,z3) != check(x4,y3,z3)) {
con.push_back(get(std::vector<int>({x3,y3,z3}),x4,0));
} // x3,y3,z3
if (check(x4,y3,z3) != check(x4,y3,z4)) {
con.push_back(get(std::vector<int>({x4,y3,z4}),z4,2));
}
if (check(x4,y3,z3) != check(x4,y4,z3)) {
con.push_back(get(std::vector<int>({x4,y3,z3}),y4,1));
}//x4,y3,z3
if (check(x3,y4,z3) != check(x3,y4,z4)) {
con.push_back(get(std::vector<int>({x3,y4,z3}),z4,2));
}
if (check(x3,y4,z3) != check(x4,y4,z3)) {
con.push_back(get(std::vector<int>({x3,y4,z3}),x4,0));
} // x3,y4,z3
if (check(x3,y3,z4) != check(x3,y4,z4)) {
con.push_back(get(std::vector<int>({x3,y3,z4}),y4,1));
}
if (check(x3,y3,z4) != check(x4,y3,z4)) {
con.push_back(get(std::vector<int>({x3,y3,z4}),x4,0));
}//x3,y3,z4
if (check(x4,y4,z3) != check(x4,y4,z4)) {
con.push_back(get(std::vector<int>({x4,y4,z3}),z4,2));
}
if (check(x4,y3,z4) != check(x4,y4,z4)) {
con.push_back(get(std::vector<int>({x4,y3,z4}),y4,1));
}
if (check(x3,y4,z4) != check(x4,y4,z4)) {
con.push_back(get(std::vector<int>({x3,y4,z4}),x4,0));
}
// for(auto i : con) {
// printf("%lf %lf %lf\n",i.x,i.y,i.z);
// }
if (con.size() < 3) {
std::cout << 0 << std::endl;
return ;
}
// return ;
std::cout << std::fixed << std::setprecision(12) <<getV() << std::endl;
}
int main(){
std::ios::sync_with_stdio(0);
freopen("in.txt","r",stdin);
while(std::cin >> x1 >> y1 >> z1) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3660kb
input:
5 4 bbobo 1 3 2 3 3 4 4 5 4 6 bobo 1 2 1 3 1 4 2 3 2 4 3 4 4 0 bobo
output:
result:
wrong answer 1st lines differ - expected: '2', found: ''