제출 #596998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
596998		andrei_boaca	The Forest of Fangorn (CEOI14_fangorn)	C++14	30 / 100	58 ms	65536 KiB

fangorn

#include <bits/stdc++.h>

using namespace std;
typedef long double ld;
mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());
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 {-1e9,-1e9};
    if(b1==0&&b2==0)
        return {-1e9,-1e9};
    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;
const ld beams=360;
const ld PI=3.14159265359;
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;
const int lim=100;
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);
        }
        shuffle(plin.begin(),plin.end(),rng);
        shuffle(gol.begin(),gol.end(),rng);
        bool ok=1;
        int cnt1=0;
        int cnt2=0;
        for(auto L1:plin)
        {
            cnt1++;
            cnt2=0;
            if(cnt1>lim)
                break;
            for(auto L2:gol)
            {
                cnt2++;
                if(cnt2>lim)
                    break;
                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;
        }
        cnt1=0,cnt2=0;
        for(int i=0;i<gol.size()&&ok&&cnt1<=lim;i++,cnt1++)
            for(int j=i+1;j<gol.size()&&ok&&cnt2<=lim;j++,cnt2++)
                {
                    line L1=gol[i];
                    line L2=gol[j];
                    point comun=intersect(L1,L2);
                    if(comun.x==-1e9&&comun.y==-1e9)
                        continue;
                    vector<int> vals;
                    if(!issame(L1.a,comun))
                    {
                        line u={G,L1.a};
                        point Ui=intersect(u,L2);
                        if(online(Ui,u))
                            vals.push_back(1);
                        else
                            vals.push_back(0);
                    }
                    if(!issame(L1.b,comun))
                    {
                        line u={G,L1.b};
                        point Ui=intersect(u,L2);
                        if(online(Ui,u))
                            vals.push_back(1);
                        else
                            vals.push_back(0);
                    }
                    if(!issame(L2.a,comun))
                    {
                        line u={G,L2.a};
                        point Ui=intersect(u,L1);
                        if(online(Ui,u))
                            vals.push_back(1);
                        else
                            vals.push_back(0);
                    }
                    if(!issame(L2.b,comun))
                    {
                        line u={G,L2.b};
                        point Ui=intersect(u,L1);
                        if(online(Ui,u))
                            vals.push_back(1);
                        else
                            vals.push_back(0);
                    }
                    bool all=1;
                    for(int i:vals)
                        if(i!=vals[0])
                            all=0;
                    if(all)
                        ok=0;
                }
        if(ok)
            sol.push_back(z);
    }
    cout<<sol.size()<<'\n';
    for(int i:sol)
        cout<<i<<' ';
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fangorn.cpp: In function 'ld panta(line)':
fangorn.cpp:74:8: warning: unused variable 'c1' [-Wunused-variable]
   74 |     ld c1=-a1*L.a.x-b1*L.a.y;
      |        ^~
fangorn.cpp: In function 'int main()':
fangorn.cpp:142:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |         for(int i=0;i<gol.size()&&ok&&cnt1<=lim;i++,cnt1++)
      |                     ~^~~~~~~~~~~
fangorn.cpp:143:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |             for(int j=i+1;j<gol.size()&&ok&&cnt2<=lim;j++,cnt2++)
      |                           ~^~~~~~~~~~~

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