QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#144976 | #2771. Need for Speed | PetroTarnavskyi# | WA | 1ms | 3516kb | C++17 | 1.5kb | 2023-08-21 20:35:02 | 2023-08-21 20:35:05 |
Judging History
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'