Submission #597047

#	Time	Username	Problem	Language	Result	Execution time	Memory
597047		andrei_boaca	The Forest of Fangorn (CEOI14_fangorn)	C++14	10 / 100	3050 ms	468 KiB

fangorn

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long double ld;
const ld EPS=1e-9;
int n,c,w,h;
struct point
{
    ld 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)
{
    ld a1=A.b.y-A.a.y;
    ld b1=A.a.x-A.b.x;
    ld c1=-a1*A.a.x-b1*A.a.y;

    ld a2=B.b.y-B.a.y;
    ld b2=B.a.x-B.b.x;
    ld 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);
    }
    ld x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
    ld y=(-c2-a2*x)/b2;
    return {x,y};
}
ld dist(point a, point b)
{
    ld 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;
ld 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)
{
    if(!inmat(a))
        return 0;
    ld d1=dist(L.a,L.b);
    ld d2=dist(L.a,a)+dist(a,L.b);
    return abs(d1-d2)<=EPS;
}
ld panta(line L)
{
    ld a1=L.b.y-L.a.y;
    ld b1=L.a.x-L.b.x;
    ld c1=-a1*L.a.x-b1*L.a.y;
    if(b1==0)
        return 1e9;
    return (-a1)/b1;
}
bool issame(point a, point b)
{
    return abs(a.x-b.x)<=EPS&&abs(a.y-b.y)<=EPS;
}
vector<line> plin,gol;
point start;
bool isbad(line L1,line L2)
{
    point comun={-1,-1};
    if(issame(L1.a,L2.a))
        comun=L1.a;
    if(issame(L1.a,L2.b))
        comun=L1.a;
    if(issame(L1.b,L2.a))
        comun=L1.b;
    if(issame(L1.b,L2.b))
        comun=L1.b;
    if(!inmat(comun))
        return 0;
    if(issame(L1.a,comun))
        swap(L1.a,L1.b);
    if(issame(L2.a,comun))
        swap(L2.a,L2.b);
    line u={G,L1.a};
    line t={G,L2.a};
    point Ui=intersect(L2,u);
    point Ti=intersect(L1,t);
    bool isu=online(Ui,u);
    bool ist=online(Ti,t);
    if(isu!=ist)
        return 0;
    else
        return 1;
}
bool comp(point a, point b)
{
    if(issame(a,start))
        return 1;
    if(issame(b,start))
        return 0;
    a.x-=start.x;
    a.y-=start.y;
    b.x-=start.x;
    b.y-=start.y;
    ld vala=0,valb=0;
    if(a.y==0)
        return 1;
    if(b.y==0)
        return 0;
    return a.x*b.y<a.y*b.x;
}
int main()
{
    cin>>w>>h;
    cin>>G.x>>G.y;
    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++)
            lines.push_back({tree[i],tree[j]});*/
    for(int z=1;z<=c;z++)
    {
        /*plin.clear();
        gol.clear();
        for(auto l:lines)
        {
            line q={G,camps[z]};
            point i=intersect(l,q);
            if(inmat(i)&&online(i,q))
                gol.push_back(l);
            else
                plin.push_back(l);
        }*/
        bool ok=1;
        /*for(int i=1;i<=n&&ok;i++)
        {
            vector<point> plin,gol;
            for(int j=1;j<=n&&ok;j++)
                if(j!=i)
                {
                    line l={tree[i],tree[j]};
                    line q={G,camps[z]};
                    point P=intersect(l,q);
                    if(inmat(P)&&online(P,q))
                        gol.push_back(tree[j]);
                    else
                        plin.push_back(tree[j]);
                }
            for(point a:plin)
                for(point b:gol)
                {
                    line L1={tree[i],a};
                    line L2={tree[i],b};
                    line u={G,L2.a};
                    line t={G,L2.b};
                    point Ui=intersect(u,L1);
                    point Ti=intersect(t,L1);
                    if(inmat(Ui)&&inmat(Ti))
                        if(online(Ui,u)&&online(Ti,t))
                        {
                            ok=0;
                            break;
                        }
                    if(!ok)
                        break;
                }
        }*/
        for(int i=1;i<=n&&ok;i++)
        {
            vector<point> points;
            for(int j=1;j<=n;j++)
                if(j!=i)
                {
                    line l={tree[i],tree[j]};
                    line q={G,camps[z]};
                    point P=intersect(l,q);
                    if(inmat(P)&&online(P,q))
                        points.push_back(tree[j]);
                }
            start={1e9,1e9};
            for(point j:points)
            {
                if(j.x<start.x)
                    start=j;
                else if(j.x==start.x&&j.y==start.y)
                    start=j;
            }
            sort(points.begin(),points.end(),comp);
            for(int j=1;j<points.size();j++)
            {
                line L1={tree[i],points[j]};
                line L2={tree[i],points[j-1]};
                if(isbad(L1,L2))
                {
                    ok=0;
                    break;
                }
            }
        }
        if(ok)
            sol.push_back(z);
    }
    cout<<sol.size()<<'\n';
    for(int i:sol)
        cout<<i<<' ';
    return 0;
}

Compilation message (stderr)

fangorn.cpp: In function 'ld panta(line)':
fangorn.cpp:71:8: warning: unused variable 'c1' [-Wunused-variable]
   71 |     ld c1=-a1*L.a.x-b1*L.a.y;
      |        ^~
fangorn.cpp: In function 'bool comp(point, point)':
fangorn.cpp:120:8: warning: unused variable 'vala' [-Wunused-variable]
  120 |     ld vala=0,valb=0;
      |        ^~~~
fangorn.cpp:120:15: warning: unused variable 'valb' [-Wunused-variable]
  120 |     ld vala=0,valb=0;
      |               ^~~~
fangorn.cpp: In function 'int main()':
fangorn.cpp:208:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |             for(int j=1;j<points.size();j++)
      |                         ~^~~~~~~~~~~~~~

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