Submission #596255

#	Time	Username	Problem	Language	Result	Execution time	Memory
596255		andrei_boaca	The Forest of Fangorn (CEOI14_fangorn)	C++14	0 / 100	225 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=360;
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;
}
double panta(line L)
{
    double a1=L.b.y-L.a.y;
    double b1=L.a.x-L.b.x;
    double c1=-a1*L.a.x-b1*L.a.y;
    if(b1==0)
        return 1e9;
    return (-a1)/b1;
}
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++)
    {
        vector<line> plin,gol;
        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(auto L1:plin)
        {
            for(auto L2:gol)
            {
                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=0;i<gol.size()&&ok;i++)
            for(int j=i+1;j<gol.size()&&ok;j++)
            {
                line L1=gol[i];
                line L2=gol[j];
                line u={G,L2.a};
                line t={G,L2.b};
                point Ui=intersect(u,L1);
                point Ti=intersect(t,L1);
                if((!online(Ui,u)||(Ui.x==L2.a.x&&Ui.y==L2.a.y))&&(!online(Ti,t)||(Ti.x==L2.b.x&&Ti.y==L2.b.y)))
                {
                    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 'double panta(line)':
fangorn.cpp:70:12: warning: unused variable 'c1' [-Wunused-variable]
   70 |     double c1=-a1*L.a.x-b1*L.a.y;
      |            ^~
fangorn.cpp: In function 'int main()':
fangorn.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int i=0;i<gol.size()&&ok;i++)
      |                     ~^~~~~~~~~~~
fangorn.cpp:120:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             for(int j=i+1;j<gol.size()&&ok;j++)
      |                           ~^~~~~~~~~~~

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