oj.uz

Submission #164485

# Submission time Handle Problem Language Result Execution time Memory
164485 2019-11-21T04:37:10 Z mhy908 The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 2279 ms 1008 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef complex<LD> point;
const LD pi=acos(-1);
point tree[2010], camp[10010], st;
bool poss[10010];
int n, c;
point get_complex()
{
    LL a, b;
    scanf("%lld %lld", &a, &b);
    return point((LD)a, (LD)b);
}
LD get_angle(point vc)
{
    LD ret=arg(vc);
    if(ret<0)ret+=2*pi;
    return ret;
}
int main()
{
    memset(poss, true, sizeof(poss));
    scanf("%*lld %*lld");
    st=get_complex();
    scanf("%d", &c);
    for(int i=1; i<=c; i++)camp[i]=get_complex();
    scanf("%d", &n);
    for(int i=1; i<=n; i++)tree[i]=get_complex();
    for(int i=1; i<=n; i++){
        LD minn=1e18, maxx=-1e18;
        for(int j=1; j<=n; j++){
            if(i==j)continue;
            LD temp=get_angle((tree[i]-tree[j])/(st-tree[i]));
            minn=min(minn, temp);
            maxx=max(maxx, temp);
        }
        for(int j=1; j<=c; j++){
            if(poss[j]){
                LD temp=get_angle((camp[j]-tree[i])/(st-tree[i]));
                if(maxx>temp&&minn<temp)poss[j]=false;
            }
        }
    }
    vector<int> ans;
    for(int i=1; i<=c; i++){
        if(poss[i])ans.pb(i);
    }
    printf("%d\n", ans.size());
    for(int i=0; i<ans.size(); i++)printf("%d ", ans[i]);
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:31:24: warning: use of assignment suppression and length modifier together in gnu_scanf format [-Wformat=]
     scanf("%*lld %*lld");
                        ^
fangorn.cpp:31:24: warning: use of assignment suppression and length modifier together in gnu_scanf format [-Wformat=]
fangorn.cpp:56:30: 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", ans.size());
                    ~~~~~~~~~~^
fangorn.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<ans.size(); i++)printf("%d ", ans[i]);
                  ~^~~~~~~~~~~
fangorn.cpp: In function 'point get_complex()':
fangorn.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
fangorn.cpp: In function 'int main()':
fangorn.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%*lld %*lld");
     ~~~~~^~~~~~~~~~~~~~~
fangorn.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &c);
     ~~~~~^~~~~~~~~~
fangorn.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 8 ms 376 KB Output is correct
12 Correct 7 ms 376 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 126 ms 504 KB Output is correct
5 Correct 30 ms 376 KB Output is correct
6 Correct 496 ms 504 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 753 ms 560 KB Output is correct
2 Correct 2279 ms 1008 KB Output is correct
3 Correct 523 ms 760 KB Output is correct
4 Correct 1690 ms 988 KB Output is correct