QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#594824#9434. Italian Cuisineucup-team4757#WA 0ms3592kbC++142.9kb2024-09-28 10:34:032024-09-28 10:34:04

Judging History

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

  • [2024-09-28 10:34:04]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3592kb
  • [2024-09-28 10:34:03]
  • 提交

answer

# include <bits/stdc++.h>

const int32_t 	   maxn = 100005;

const long double  eps  = 1e-10;

int32_t n;

struct point {
	int64_t x, y;
	
	inline long double len () {
		return std::sqrt (x * x + y * y);
	}
} center;

inline int64_t operator ^ (const point & a, const point & b) {
	return a.x * b.y - b.x * a.y;
}

inline point operator - (const point & a, const point & b) {
	return (point) {a.x - b.x, a.y - b.y};
}

int64_t rad = 0;

struct triangle {
	point p[3];
	
	inline int64_t size () {
		return std::abs ((p[2] - p[1]) ^ (p[0] - p[1]));
	}
};

struct polygon {
	std::vector <point> p;
	
	inline polygon () {
		p.clear ();
	}
	
	inline void push_back (const point a) {
		p.push_back (a);
	}
};

int32_t end[maxn];

inline bool cmp (const int64_t sdis, const long double rdis) {
	return rdis + eps > sdis;
}

inline long double dis (const point src, const point des, const point p) {
//	std::cerr << ((p - src) ^ (des - src)) << '\n';
	return fabs (1.0 * ((p - src) ^ (des - src)) / (des - src).len ());
}

inline bool left (const point src, const point des, const point p) {
	return cmp (0, 1.0 * ((p - src) ^ (des - src)) / (des - src).len ());
}

inline int32_t nxt (const int32_t x, const int32_t p = n) {
	return x == p ? 1 : x + 1; 
}

inline int32_t lst (const int32_t x, const int32_t p = n) {
	return x == 1 ? p : x - 1; 
}

int64_t sizenow = 0, sizemax = 0;

inline void mfind (const polygon & a, const int32_t p, int32_t & h) {
	
	// std::cerr << "bg " << sizenow << '\n';
	
//	if (p == h) h = nxt (h), sizenow = sizenow + ((triangle) {a.p[h - 1], a.p[lst (h) - 1], a.p[p - 1]}).size (), sizemax = std::max (sizemax, sizenow), std::cerr << "add " << h << ' ' << lst (h) << ' ' << p << '\n';
	
	// std::cerr << "md " << sizenow << '\n';
	
	while (left (a.p[nxt (h) - 1], a.p[p - 1], center) && cmp (rad, dis (a.p[nxt (h) - 1], a.p[p - 1], center)))
		h = nxt (h), sizenow = sizenow + ((triangle) {a.p[h - 1], a.p[lst (h) - 1], a.p[p - 1]}).size (), sizemax = std::max (sizemax, sizenow);
//		std::cerr << "add " << h << ' ' << lst (h) << ' ' << p << '\n';
		
	end[p] = h;
	
	// std::cerr << "ed " << sizenow << '\n';
}

int32_t x, y, now = 0;

inline void Solve (const int32_t Case) {
	
	polygon a;
	
	std::cin >> n;
	
	center = {0, 0}, rad = 0, now = 1, sizenow = sizemax = 0;
	
	std::cin >> center.x >> center.y >> rad;
	
	for (int i = 1; i <= n; ++ i)
		std::cin >> x >> y, a.push_back ({x, y});
	
	for (int i = 1; i <= n; ++ i) {
		mfind (a, i, now);
		sizenow = sizenow - ((triangle) {a.p[nxt (i) - 1], a.p[i - 1], a.p[now - 1]}).size ();
	}
	
	std::cout << sizemax << '\n';
	
//	for (int i = 1; i <= n; ++ i) std::cerr << end[i] << '\n';
	
}

int32_t T;

int main () {
	
	std::ios::sync_with_stdio (0);
	std::cin.tie (0), std::cout.tie (0);
	
	std::cin >> T;
	
	for (int i = 1; i <= T; ++ i) Solve (i);
	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3536kb

input:

3
5
1 1 1
0 0
1 0
5 0
3 3
0 5
6
2 4 1
2 0
4 0
6 3
4 6
2 6
0 3
4
3 3 1
3 0
6 3
3 6
0 3

output:

5
24
0

result:

ok 3 number(s): "5 24 0"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3592kb

input:

1
6
0 0 499999993
197878055 -535013568
696616963 -535013568
696616963 40162440
696616963 499999993
-499999993 499999993
-499999993 -535013568

output:

286862654137719264

result:

wrong answer 1st numbers differ - expected: '0', found: '286862654137719264'