Submission #95930

#	Time	Username	Problem	Language	Result	Execution time	Memory
95930		Bodo171	The Forest of Fangorn (CEOI14_fangorn)	C++14	0 / 100	397 ms	532 KiB

fangorn

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

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 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 20