QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288456#5649. Spinach PizzaSorting#WA 1ms3504kbC++201.5kb2023-12-22 18:05:172023-12-22 18:05:19

Judging History

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

  • [2023-12-22 18:05:19]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3504kb
  • [2023-12-22 18:05:17]
  • 提交

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}));
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

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