oj.uz

Submission #95930

# Submission time Handle Problem Language Result Execution time Memory
95930 2019-02-04T12:37:50 Z Bodo171 The Forest of Fangorn (CEOI14_fangorn) C++14
0 / 100
 397 ms 532 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;
const int nmax=2005;
vector<int> ans;
struct point
{
    long long x,y;
}orig,q[5*nmax],st[nmax],dr[nmax],v[nmax],a[nmax],G;
int n,i,w,h,Q,nr,j;
long long det(point A,point B,point C)
{
    return (1LL*A.x*B.y+B.x*C.y+C.x*A.y-A.y*B.x-B.y*C.x-C.y*A.x);
}
long long sgn(long long x)
{
    if(x<0) return -1;
    if(x>0) return 1;
    return 0;
}
bool trigo(point A,point B)
{
    return (sgn(det(orig,A,B))==1);
}
bool check(int poz)
{
    for(int i=1;i<=n;i++)
    {
        if(det(st[i],q[poz],dr[i])<=1LL*0)
            return 0;
    }
    return 1;
}
point refl(point O,point a)
{
    a.x=O.x+(O.x-a.x);
    a.y=O.y+(O.y-a.y);
    return a;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>w>>h;
    cin>>G.x>>G.y;
    cin>>Q;
    for(i=1;i<=Q;i++)
    {
        cin>>q[i].x>>q[i].y;
    }
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
    }
    for(i=1;i<=n;i++)
    {
        nr=0;
        for(j=1;j<=n;j++)
            if(i!=j)
              {
                  a[++nr]=refl(v[i],v[j]);
              }
        orig=v[i];
        sort(a+1,a+nr+1,trigo);
        a[n]=a[1];
        for(j=1;j<n;j++)
        {
            if(sgn(det(a[j],G,a[j+1]))==1)//vezi aici
            {
                st[i]=a[j];
                dr[i]=a[j+1];
            }
        }
    }
    for(int cnt=1;cnt<=Q;cnt++)
    {
        if(check(cnt))
            ans.push_back(cnt);
    }
    cout<<ans.size()<<'\n';
    for(int i=0;i<ans.size();i++)
        cout<<ans[i]<<' ';
    return 0;
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ans.size();i++)
                 ~^~~~~~~~~~~

Subtask #1
0.0 / 30.0

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

Subtask #2
0.0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 20.0

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