oj.uz

Submission #25950

# Submission time Handle Problem Language Result Execution time Memory
25950 2017-06-25T07:53:35 Z 시제연(#1089) The Forest of Fangorn (CEOI14_fangorn) C++
0 / 100
 1483 ms 44152 KB 
#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

int n, c, w, h;
pll tree[2100];
pll camp[10100];
short lab[10100][2100];
pll st;

vector<pll> tec, oec;

ll ccw (pll a, pll b) {return a.x*b.y-a.y*b.x;}

int wh(pll a) {
    if (a.x>0||(a.x==0&&a.y>0)) return 0;
    return 1;
}

bool cmpp(pll A, pll B) {
    return wh(A)!=wh(B)?wh(A)<wh(B):ccw(A,B)>0;
}

pll operator - (pll &A, pll &B) {
    return pll(A.x-B.x,A.y-B.y);
}

bool cmp(int a, int b) {
    return cmpp(oec[a],oec[b]);
}

int ord[10100];
void solve(int idx) {
    int i, j;
    tec.clear();
    for (i=0;i<n;i++) {
        if (i==idx) continue;
        tec.push_back(tree[idx]-tree[i]);
    }
    sort(tec.begin(),tec.end(),cmpp);
    i=j=0;
    while(i<tec.size()||j<c) {
        if (i==tec.size()) lab[ord[j++]][idx] = i%(n-1);
        else if (j==c+1) i++;
        else if (cmpp(tec[i],camp[ord[j]]-tree[idx])) i++;
        else lab[ord[j++]][idx] = i%(n-1);
    }
}

void solve2(int idx) {
    int i;
    tec.clear();
    for (i=0;i<n;i++) {
        if (i==idx) continue;
        tec.push_back(tree[idx]-tree[i]);
    }
    sort(tec.begin(),tec.end(),cmpp);
    for (i=0;i<n-1;i++) if (cmpp(st-tree[idx],tec[i])) break;
    lab[c][idx] = i%(n-1);
}

int main() {
    int i, j;

    scanf("%d%d",&w,&h);
    scanf("%lld%lld\n",&st.x,&st.y);
    scanf("%d",&c);
    for (i=0;i<c;i++) scanf("%d%d",&camp[i].x,&camp[i].y);
    camp[c] = st;
    scanf("%d",&n);
    for (i=0;i<n;i++) scanf("%d%d",&tree[i].x,&tree[i].y);

    for (i=0;i<c;i++) oec.push_back(camp[i]-tree[0]);
    for (i=0;i<c;i++) ord[i] = i;
    sort(ord,ord+c,cmp);

    for (i=0;i<n;i++) solve(i);
    for (i=0;i<n;i++) solve2(i);

    vector<int> res;
    for (i=0;i<c;i++) {
        bool flag = true;
        for (j=0;j<n;j++) if (lab[i][j]!=lab[c][j]) flag = false;
        if (flag) res.push_back(i+1);
    }
    printf("%d\n",res.size());
    for (i=0;i<res.size();i++) printf("%d ",res[i]);
    printf("\n");

    return 0;
}

Compilation message

fangorn.cpp: In function 'void solve(int)':
fangorn.cpp:48:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i<tec.size()||j<c) {
            ^
fangorn.cpp:49:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i==tec.size()) lab[ord[j++]][idx] = i%(n-1);
              ^
fangorn.cpp: In function 'int main()':
fangorn.cpp:74:57: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     for (i=0;i<c;i++) scanf("%d%d",&camp[i].x,&camp[i].y);
                                                         ^
fangorn.cpp:74:57: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
fangorn.cpp:77:57: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     for (i=0;i<n;i++) scanf("%d%d",&tree[i].x,&tree[i].y);
                                                         ^
fangorn.cpp:77:57: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
fangorn.cpp:92:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n",res.size());
                             ^
fangorn.cpp:93:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<res.size();i++) printf("%d ",res[i]);
               ^
fangorn.cpp:71:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&w,&h);
                        ^
fangorn.cpp:72:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld\n",&st.x,&st.y);
                                    ^
fangorn.cpp:73:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&c);
                   ^
fangorn.cpp:74:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i=0;i<c;i++) scanf("%d%d",&camp[i].x,&camp[i].y);
                                                          ^
fangorn.cpp:76:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
fangorn.cpp:77:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i=0;i<n;i++) scanf("%d%d",&tree[i].x,&tree[i].y);
                                                          ^

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 43684 KB Output is correct
2 Correct 0 ms 43684 KB Output is correct
3 Correct 0 ms 43684 KB Output is correct
4 Incorrect 0 ms 43684 KB Output isn't correct
5 Incorrect 0 ms 43684 KB Output isn't correct
6 Correct 0 ms 43684 KB Output is correct
7 Correct 0 ms 43684 KB Output is correct
8 Correct 0 ms 43684 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 43684 KB Output is correct
2 Incorrect 0 ms 43684 KB Output isn't correct
3 Incorrect 0 ms 43684 KB Output isn't correct
4 Correct 0 ms 43684 KB Output is correct
5 Correct 0 ms 43684 KB Output is correct
6 Correct 3 ms 43684 KB Output is correct
7 Correct 0 ms 43684 KB Output is correct
8 Correct 0 ms 43684 KB Output is correct
9 Correct 0 ms 43684 KB Output is correct
10 Incorrect 3 ms 43684 KB Output isn't correct
11 Correct 6 ms 43684 KB Output is correct
12 Correct 6 ms 43684 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 43684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1106 ms 43824 KB Output is correct
2 Incorrect 1483 ms 44152 KB Output isn't correct
3 Halted 0 ms 0 KB -