Submission #596047

#	Time	Username	Problem	Language	Result	Execution time	Memory
596047		andrei_boaca	The Forest of Fangorn (CEOI14_fangorn)	C++14	0 / 100	500 ms	65536 KiB

fangorn

#include <bits/stdc++.h>

using namespace std;
const double EPS=1e-9;
int n,c,w,h;
struct point
{
    double x,y;
} G,camps[10005],tree[10005];
struct line
{
    point a,b;
};
vector<line> lines;
bool inmat(point p)
{
    return p.x>=0&&p.x<=w&&p.y>=0&&p.y<=h;
}
point intersect(line A, line B)
{
    double a1=A.b.y-A.a.y;
    double b1=A.a.x-A.b.x;
    double c1=-a1*A.a.x-b1*A.a.y;

    double a2=B.b.y-B.a.y;
    double b2=B.a.x-B.b.x;
    double c2=-a2*B.a.x-b2*B.a.y;

    if(a1==0&&a2==0)
        return {-1,-1};
    if(b1==0&&b2==0)
        return {-1,-1};
    if(b2==0)
    {
        swap(a1,a2);
        swap(b1,b2);
        swap(c1,c2);
    }
    double x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
    double y=(-c2-a2*x)/b2;
    return {x,y};
}
double dist(point a, point b)
{
    double val=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    return sqrt(val);
}
vector<int> mylines,sol,Glines;
bool conv=0;
const double beams=180;
const double PI=3.14159265359;
double aria(point a, point b, point c)
{
    a.x-=c.x;
    a.y-=c.y;
    b.x-=c.x;
    b.y-=c.y;
    return a.x*b.y-a.y*b.x;
}
bool online(point a, line L)
{
    double d1=dist(L.a,L.b);
    double d2=dist(L.a,a)+dist(a,L.b);
    return abs(d1-d2)<=EPS;
}
bool prt=0;
void laser(point p)
{
    mylines.clear();
    conv=1;
    double grade=0,rad=0;
    double ip=10.0;
    vector<bool> f;
    f.resize((int)lines.size());
    vector<point> ups,downs,poli;
    while(grade<=beams)
    {
        double x=ip*cos(rad)+p.x;
        double y=ip*sin(rad)+p.y;
        point q={x,y};
        point up={1e9,1e9},down={-1e9,-1e9};
        int lup=-1,ldown=-1;
        line l={p,q};
        for(int i=0;i<lines.size();i++)
        {
            point a=intersect(l,lines[i]);
            if(inmat(a)&&online(a,lines[i]))
            {
                if(a.y>=p.y+EPS&&a.y<up.y)
                {
                    up=a;
                    lup=i;
                }
                if(a.y<=p.y-EPS&&a.y>down.y)
                {
                    down=a;
                    ldown=i;
                }
            }
        }
        if(lup>=0&&f[lup]==0)
        {
            f[lup]=1;
            mylines.push_back(lup);
            ups.push_back(up);
        }
        if(ldown>=0&&f[ldown]==0)
        {
            f[ldown]=1;
            mylines.push_back(ldown);
            downs.push_back(down);
        }
        grade++;
        rad+=PI/beams;
    }
    reverse(downs.begin(),downs.end());
    for(auto i:ups)
        poli.push_back(i);
    for(auto i:downs)
        poli.push_back(i);
    sort(mylines.begin(),mylines.end());
    mylines.erase(unique(mylines.begin(),mylines.end()),mylines.end());
    if(prt)
    {
        /*for(auto i:poli)
            cout<<i.x<<' '<<i.y<<'\n';*/
        /*for(auto i:mylines)
        {
            line l=lines[i];
            cout<<l.a.x<<' '<<l.a.y<<' '<<l.b.x<<' '<<l.b.y<<'\n';
        }
        cout<<'\n';*/
    }
    conv=1;
    for(int i=2;i<poli.size();i++)
    {
        point a=poli[i-2];
        point b=poli[i-1];
        point c=poli[i];
        /*if(prt)
            cout<<aria(a,b,c)<<'\n';*/
        if(aria(a,b,c)>0)
        {
            conv=0;
            break;
        }
    }
}
int main()
{
    cin>>w>>h;
    cin>>G.x>>G.y;
    lines.push_back({{0,0},{0,h}});
    lines.push_back({{0,0},{w,0}});
    lines.push_back({{w,h},{0,h}});
    lines.push_back({{w,h},{w,0}});
    cin>>c;
    for(int i=1;i<=c;i++)
        cin>>camps[i].x>>camps[i].y;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>tree[i].x>>tree[i].y;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            line l={tree[i],tree[j]};
            for(int p=0;p<4;p++)
            {
                point a=intersect(lines[p],l);
                if(inmat(a))
                {
                    double d=dist(tree[i],a)+dist(tree[i],tree[j]);
                    double d2=dist(tree[j],a);
                    if(abs(d-d2)<=EPS)
                        lines.push_back({tree[i],a});
                    else
                        lines.push_back({tree[j],a});
                }
            }
        }
    laser(G);
    if(conv==0)
        mylines.clear();
    else
    {
        Glines=mylines;
        sort(Glines.begin(),Glines.end());
        Glines.erase(unique(Glines.begin(),Glines.end()),Glines.end());
    }
    for(int i=1;i<=c;i++)
    {
        if(i==2)
            prt=1;
        else
            prt=0;
        laser(camps[i]);
        if(conv)
        {
            if(Glines.empty())
                continue;
            sort(mylines.begin(),mylines.end());
            mylines.erase(unique(mylines.begin(),mylines.end()),mylines.end());
            if(mylines.size()==Glines.size())
            {
                bool ok=1;
                for(int j=0;j<mylines.size();j++)
                    if(mylines[j]!=Glines[j])
                        ok=0;
                if(ok)
                    sol.push_back(i);
            }
        }
        else
        {
            if(Glines.empty())
                sol.push_back(i);
        }
    }
    cout<<sol.size()<<'\n';
    for(int i:sol)
        cout<<i<<' ';
    return 0;
}

Compilation message (stderr)

fangorn.cpp: In function 'void laser(point)':
fangorn.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(int i=0;i<lines.size();i++)
      |                     ~^~~~~~~~~~~~~
fangorn.cpp:135:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for(int i=2;i<poli.size();i++)
      |                 ~^~~~~~~~~~~~
fangorn.cpp: In function 'int main()':
fangorn.cpp:153:31: warning: narrowing conversion of 'h' from 'int' to 'double' [-Wnarrowing]
  153 |     lines.push_back({{0,0},{0,h}});
      |                               ^
fangorn.cpp:154:29: warning: narrowing conversion of 'w' from 'int' to 'double' [-Wnarrowing]
  154 |     lines.push_back({{0,0},{w,0}});
      |                             ^
fangorn.cpp:155:23: warning: narrowing conversion of 'w' from 'int' to 'double' [-Wnarrowing]
  155 |     lines.push_back({{w,h},{0,h}});
      |                       ^
fangorn.cpp:155:25: warning: narrowing conversion of 'h' from 'int' to 'double' [-Wnarrowing]
  155 |     lines.push_back({{w,h},{0,h}});
      |                         ^
fangorn.cpp:155:31: warning: narrowing conversion of 'h' from 'int' to 'double' [-Wnarrowing]
  155 |     lines.push_back({{w,h},{0,h}});
      |                               ^
fangorn.cpp:156:23: warning: narrowing conversion of 'w' from 'int' to 'double' [-Wnarrowing]
  156 |     lines.push_back({{w,h},{w,0}});
      |                       ^
fangorn.cpp:156:25: warning: narrowing conversion of 'h' from 'int' to 'double' [-Wnarrowing]
  156 |     lines.push_back({{w,h},{w,0}});
      |                         ^
fangorn.cpp:156:29: warning: narrowing conversion of 'w' from 'int' to 'double' [-Wnarrowing]
  156 |     lines.push_back({{w,h},{w,0}});
      |                             ^
fangorn.cpp:206:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |                 for(int j=0;j<mylines.size();j++)
      |                             ~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 20