QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#144976#2771. Need for SpeedPetroTarnavskyi#WA 1ms3516kbC++171.5kb2023-08-21 20:35:022023-08-21 20:35:05

Judging History

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

  • [2023-08-21 20:35:05]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3516kb
  • [2023-08-21 20:35:02]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = int(a); i < int(b); i++)
#define RFOR(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)

#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define FILL(a, b) memset(a, b, sizeof(a))
#define S second
#define F first


typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long double db;

struct Point 
{
	LL x, y;
	Point() {}
	Point(LL _x, LL _y): x(_x), y(_y) {}
	Point operator-(const Point& p) const {
		return {x - p.x, y - p.y};
	}
	LL operator*(const Point& p) const {
		return x * p.y - p.x * y;
	}
	bool operator <(const Point& p) const
	{
		return x == p.x ? y < p.y : x < p.x;
	}
};

const int INF = 1000'000'447;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<pair<Point, int>> v(n + m);
	FOR (i, 0, n) 
	{
		cin >> v[i].F.x >> v[i].F.y;
		v[i].S = 0;
	}
	FOR (i, 0, m)
	{
		cin >> v[i + n].F.x >> v[i + n].F.y;
		v[i].S = 0;
	}
	sort(ALL(v));
	vector<Point> p1;
	vector<Point> p2;
	LL ans = 0;
	FOR (i, 0, n + m)
	{
		if (v[i].S == 0)
		{
			p2.PB({v[i].F.x, p1.empty() ? INF : p1.back().y});
			p1.PB(v[i].F);
		}
		else if (!p1.empty())
		{
			int l = 0;
			int r = SZ(p1);
			while (l + 1 < r)
			{
				int mid = (l + r) / 2;
				if (p2[mid] * v[i].F <= 0)
					l = mid;
				else
					r = mid;
			}
			ans = max(ans, (v[i].F.x - p1[l].x) * (v[i].F.y - p1[l].y));
		}
	}
	cout << ans << '\n';
}


詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3516kb

input:

3 5
4 -1
4 0
10 3

output:

0

result:

wrong answer 1st numbers differ - expected: '3.0000000', found: '0.0000000', error = '1.0000000'