QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#288456 | #5649. Spinach Pizza | Sorting# | WA | 1ms | 3504kb | C++20 | 1.5kb | 2023-12-22 18:05:17 | 2023-12-22 18:05:19 |
Judging History
answer
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
using namespace std;
typedef long long ll;
struct Point{
ll x, y;
int idx;
friend bool operator<(const Point &l, const Point &r){
return l.idx < r.idx;
}
friend bool operator==(const Point &l, const Point &r){
return l.idx == r.idx;
}
};
const int N = 100 + 3;
int n;
vector<Point> p;
ll area2(Point a, Point b, Point c){
return a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y;
}
pair<ll, int> smallest(vector<Point> p){
pair<ll, int> answer;
answer.first = 2e18;
for(int i = 0; i < p.size(); ++i){
int prv = (i - 1 + (int)p.size()) % p.size();
int nxt = (i + 1) % p.size();
pair<ll, int> cand;
cand.first = area2(p[prv], p[i], p[nxt]);
cand.second = i;
answer = min(answer, cand);
}
return answer;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
p.resize(n);
for(int i = 0; i < n; ++i){
cin >> p[i].x >> p[i].y;
p[i].idx = i + 1;
}
cout << "Alberto" << endl;
for(int turn = 0; turn < n - 2; ++turn){
if(turn % 2 == 0){
auto small = smallest(p);
cout << p[small.second].idx << endl;
p.erase(p.begin() + small.second);
}
else{
int idx;
cin >> idx;
p.erase(find(p.begin(), p.end(), Point{0, 0, idx}));
}
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3452kb
input:
4 0 0 6 1 5 3 1 4 4
output:
Alberto 3
result:
ok they win, their_area 7 <= our_area 23. Used strategy 0
Test #2:
score: 0
Accepted
time: 1ms
memory: 3460kb
input:
6 0 0 2 0 3 2 2 4 0 4 -1 2 3 6
output:
Alberto 1 5
result:
ok they win, their_area 8 <= our_area 16. Used strategy 0
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3504kb
input:
7 0 0 2 0 5 2 4 5 1 5 -1 4 -1 2 5 4
output:
Alberto 7 2 1
result:
wrong answer they lose, their_area 28 > our_area 19. Used strategy 0