QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#245022#2827. AutobiographyDelay_for_five_minutes#WA 1ms3660kbC++114.9kb2023-11-09 17:55:122023-11-09 17:55:13

Judging History

你现在查看的是最新测评结果

  • [2023-11-09 17:55:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3660kb
  • [2023-11-09 17:55:12]
  • 提交

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();
	}
}

詳細信息

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: ''