QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#772165#7906. Almost ConvexwangjunruiWA 1ms4132kbC++142.8kb2024-11-22 17:17:392024-11-22 17:17:40

Judging History

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

  • [2024-11-22 17:17:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4132kb
  • [2024-11-22 17:17:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e3 + 5;
typedef long long ll;
int n;
struct node
{
	int x, y;
	node(int _x = 0, int _y = 0) : x(_x), y(_y) {}
	inline ll operator*(const node &rhs) const
	{
		return (ll)x * rhs.y - (ll)y * rhs.x;
	}
	inline double get()
	{
		return atan2(y, x);
	}
	inline node operator+(const node &rhs) const
	{
		return node(x + rhs.x, y + rhs.y);
	}
	inline node operator-(const node &rhs) const
	{
		return node(x - rhs.x, y - rhs.y);
	}
} a[N];
int b[N], m;
int c[N], q;
bool vis[N];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		int x, y;
		cin >> x >> y;
		a[i] = node(x, y);
	}
	swap(a[1], *min_element(a + 1, a + 1 + n, [](node x, node y)
		{
			return x.x < y.x;
		}));
	sort(a + 2, a + 1 + n, [](node x, node y)
		{
			return (x - a[1]).get() < (y - a[1]).get();
		});
	b[m = 1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		while (m > 1 && (a[b[m - 1]] - a[b[m]]) * (a[i] - a[b[m]]) >= 0)
			--m;
		b[++m] = i;
	}
	while (m > 1 && (a[b[m - 1]] - a[b[m]]) * (a[1] - a[b[m]]) >= 0)
		--m;
	int cnt = 1;
	for (int i = 1; i <= n; ++i)
		vis[b[i]] = true;
	for (int i = 1; i <= n; ++i)
	{
		if (vis[i])
			continue;
		q = 0;
		for (int j = 1; j <= n; ++j)
		{
			if (vis[j] || i == j)
				continue;
			c[++q] = j;
		}
		sort(b + 1, b + 1 + m, [&](int x, int y)
			{
				return (a[x] - a[i]).get() < (a[y] - a[i]).get();
			});
		
		sort(c + 1, c + 1 + q, [&](int x, int y)
			{
				return (a[x] - a[i]).get() < (a[y] - a[i]).get();
			});
		for (int j = 1, l = 1, r = 1; j < m; ++j)
		{
			while (l <= q && (a[c[l]] - a[i]).get() <= (a[b[j]] - a[i]).get())
				++l;
			while (r <= q && (a[c[r]] - a[i]).get() < (a[b[j + 1]] - a[i]).get())
				++r;	
			if (l < r)
			{
				bool flag = true;
				ll area = abs((a[b[j]] - a[i]) * (a[b[j + 1]] - a[i]));
				for (int k = l; k <= r; ++k)
				{
					ll x = abs((a[c[k]] - a[i]) * (a[c[k]] - a[b[j]]));
					ll y = abs((a[c[k]] - a[i]) * (a[c[k]] - a[b[j + 1]]));
					ll z = abs((a[c[k]] - a[b[j]]) * (a[c[k]] - a[b[j + 1]]));
					if (x + y + z == area && x && y)
					{
						flag = false;
						break;
					}
				}
				cnt += flag;
			}
			else
				++cnt;
		}
		bool flag = true;
		ll area = abs((a[b[m]] - a[i]) * (a[b[1]] - a[i]));
		for (int k = 1; k <= q; ++k)
		{
			if ((a[c[k]] - a[i]).get() > (a[b[m]] - a[i]).get()
				|| (a[c[k]] - a[i]).get() < (a[b[1]] - a[i]).get())
			{
				ll x = abs((a[c[k]] - a[i]) * (a[c[k]] - a[b[m]]));
				ll y = abs((a[c[k]] - a[i]) * (a[c[k]] - a[b[1]]));
				ll z = abs((a[c[k]] - a[b[m]]) * (a[c[k]] - a[b[1]]));
				if (x + y + z == area && x && y)
				{
					flag = false;
					break;
				}
			}
		}
		cnt += flag;
	}
	cout << cnt << '\n';
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4132kb

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 4132kb

input:

5
4 0
0 0
2 1
3 3
3 1

output:

4

result:

wrong answer 1st numbers differ - expected: '5', found: '4'