Submission #25968

#	Time	Username	Problem	Language	Result	Execution time	Memory
25968		tlwpdus	The Forest of Fangorn (CEOI14_fangorn)	C++98	100 / 100	1366 ms	44192 KiB

fangorn

#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];
int vrd[10100];
void solve(int idx) {
    int i, j, jdx;
    tec.clear();
    for (i=0;i<n;i++) {
        if (i==idx) continue;
        tec.push_back(tree[idx]-tree[i]);
    }
    for (i=0;i<c-1;i++) if (cmpp(camp[ord[i+1]]-tree[idx],camp[ord[i]]-tree[idx])) break;
    if (i!=c-1) rotate(ord,ord+i+1,ord+c);
    for (i=0;i<c;i++) vrd[i] = ord[i];
    for (jdx=0;jdx<c;jdx++) if (cmpp(st-tree[idx],camp[ord[jdx]]-tree[idx])) break;
    for (i=c;i>jdx;i--) vrd[i] = vrd[i-1];
    vrd[jdx] = c;
    sort(tec.begin(),tec.end(),cmpp);
    i=j=0;
    while(i<tec.size()||j<=c) {
        if (i==tec.size()) lab[vrd[j++]][idx] = i%(n-1);
        else if (j==c+1) i++;
        else if (cmpp(tec[i],camp[vrd[j]]-tree[idx])) i++;
        else lab[vrd[j++]][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);

    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 (stderr)

fangorn.cpp: In function 'int wh(pll)':
fangorn.cpp:22:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (a.x>0||a.x==0&&a.y>0) return 0;
                      ^
fangorn.cpp: In function 'void solve(int)':
fangorn.cpp:55:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i<tec.size()||j<=c) {
            ^
fangorn.cpp:56:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i==tec.size()) lab[vrd[j++]][idx] = i%(n-1);
              ^
fangorn.cpp: In function 'int main()':
fangorn.cpp:69: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:69:57: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
fangorn.cpp:72: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:72:57: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
fangorn.cpp:89: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:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<res.size();i++) printf("%d ",res[i]);
               ^
fangorn.cpp:66: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:67: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:68:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&c);
                   ^
fangorn.cpp:69: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:71:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
fangorn.cpp:72: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: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 20 / 20