백준5178 시간 초과

작성일 | In

문제 링크

  • http://icpc.me/5178

사용 알고리즘

  • Convex Hull

풀이

일단 적절히 파싱해서 x와 y로 이루어진 단항식들을 모두 구해줍시다.

각 단항식의 (x의 지수, y의 지수)를 2차원 평면 상에 플로팅해주고 Convex Hull 윗껍질의 오른쪽 부분을 구해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

int pv;
vector<string> v;
vector<p> pt;
int chk[55][55];

ll ccw(const p &a, const p &b, const p &c){
    ll dx1 = b.x - a.x, dy1 = b.y - a.y;
    ll dx2 = c.x - b.x, dy2 = c.y - b.y;
    return dx1*dy2 - dx2*dy1;
}

ll dst(const p &a, const p &b){
    ll dx = b.x - a.x, dy = b.y - a.y;
    return dx*dx + dy*dy;
}

vector<p> convex_hull(vector<p> &v){
    vector<p> ret;
    swap(v[0], *min_element(all(v)));
    sort(v.begin()+1, v.end(), [&](const p &a, const p &b){
        auto cw = ccw(v[0], a, b);
        if(cw) return cw > 0;
        return dst(v[0], a) < dst(v[0], b);
    });
    for(const auto &i : v){
        while(ret.size() >= 2 && ccw(ret[ret.size()-2], ret.back(), i) <= 0) ret.pop_back();
        ret.push_back(i);
    }
    return ret;
}

void solve(){
    cout << "Data Set " << ++pv << ":\n";
    pt.clear();
    memset(chk, 0, sizeof chk);
    stack<int> stk, save; int cnt[2] = {0}, now = 0;
    int cnst = 1;
    for(auto i : v){
        if(i == "loop x"){ stk.push(0); save.push(now); now = 0; cnt[0]++; }
        if(i == "loop y"){ stk.push(1); save.push(now); now = 0; cnt[1]++; }
        if(i == "basic"){ now = 1; }
        if(i == "endloop"){
            if(now) cnst = 0, chk[cnt[0]][cnt[1]] = 1;
            now = save.top(); save.pop();
            cnt[stk.top()]--; stk.pop();
        }
    }
    pt.emplace_back(0, 0);
    for(int i=50; ~i; i--){
        for(int j=50; ~j; j--){
            if(chk[i][j]){ pt.emplace_back(i, j); break; }
        }
    }

    if(cnst){ cout << now << "\n"; return; }
    auto hull = convex_hull(pt);
    int st = 0;
    for(int i=0; i<hull.size(); i++) if(hull[i] > hull[st]) st = i;
    int flag = 0;
    for(int i=st; i<hull.size(); i++){
        if(st != i && hull[i-1].y >= hull[i].y) break;
        if(flag) cout << " + "; flag = 1;

        if(hull[i].x) cout << "x";
        if(hull[i].x > 1) cout << "^" << hull[i].x;
        if(hull[i].y) cout << "y";
        if(hull[i].y > 1) cout << "^" << hull[i].y;
    }
    cout << "\n";
}

int main(){
    char op[11], c;
    int t; string s; scanf("%d", &t);
    while(t--){
        while(1){
            scanf("%s", op);
            s = string(op);
            if(s == "endprogram") break;
            if(s == "loop"){
                scanf(" %c", &c);
                if(c == 'x') s = "loop x";
                else s = "loop y";
            }
            v.push_back(s);
        }
        solve(); v.clear();
        cout << "\n";
    }
}