QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#297703	#7511. Planar Graph	sofija6	WA	43ms	223884kb	C++23	7.3kb	2024-01-05 00:42:24	2024-01-05 00:42:24

Judging History

你现在查看的是最新测评结果

[2024-01-05 00:42:24]
评测

测评结果：WA
用时：43ms
内存：223884kb

查看

[2024-01-05 00:42:24]
提交

answer

#include <bits/stdc++.h>
#define ll long long
#define MAXN 3010
using namespace std;
struct point
{
    ll x,y;
};
struct segment
{
    point a,b;
};
struct triangle
{
    ll ia,ib,ic;
};
segment Sortt(segment s)
{
    if (s.a.x>s.b.x || (s.a.x==s.b.x && s.a.y>s.b.y))
        swap(s.a,s.b);
    return s;
}
ll Cross(point C,point B,point A)
{
    ll val=(B.x-C.x)*(A.y-C.y)-(B.y-C.y)*(A.x-C.x);
    if (val>0)
        return 1;
    if (val<0)
        return -1;
    return 0;
}
pair<pair<ll,ll>,pair<ll,ll> > Make_Pair(segment A)
{
    return {{A.a.x,A.a.y},{A.b.x,A.b.y}};
}
bool Intersect(segment A,segment B)
{
    if (A.a.x==B.a.x && A.a.y==B.a.y)
        return false;
    if (A.b.x==B.b.x && A.b.y==B.b.y)
        return false;
    if (A.a.x==B.b.x && A.a.y==B.b.y)
        return false;
    if (A.b.x==B.a.x && A.b.y==B.a.y)
        return false;
    return Cross(A.a,A.b,B.a)!=Cross(A.a,A.b,B.b) && Cross(B.a,B.b,A.a)!=Cross(B.a,B.b,A.b);
}
bool Cmp(pair<segment,ll> A,pair<segment,ll> B)
{
    return Make_Pair(A.first)<Make_Pair(B.first);
}
vector<segment> v,u;
vector<triangle> t;
set<pair<pair<ll,ll>,pair<ll,ll> > > mv,mu;
vector<pair<segment,ll> > side;
bool Exist(segment A)
{
    pair<pair<ll,ll>,pair<ll,ll> > p=Make_Pair(A);
    return (mv.count(p) || mu.count(p));
}
point b[MAXN],s[MAXN];
vector<ll> G[MAXN*MAXN];
bool has[MAXN*MAXN],V[MAXN*MAXN],in[MAXN];
ll ans[MAXN],edge[MAXN][MAXN];
vector<pair<ll,ll> > vi;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m,e;
    cin >> n >> m >> e;
    for (ll i=1;i<=n;i++)
        cin >> b[i].x >> b[i].y;
    for (ll i=1;i<=m;i++)
        cin >> s[i].x >> s[i].y;
    for (ll i=1;i<=e;i++)
    {
        ll p,q;
        cin >> p >> q;
        v.push_back({b[p],b[q]});
        mv.insert(Make_Pair({b[p],b[q]}));
        mv.insert(Make_Pair({b[q],b[p]}));
        edge[p][q]=i;
        edge[q][p]=i;
        vi.push_back({p,q});
    }
    for (ll i=1;i<=n;i++)
    {
        for (ll j=i+1;j<=n;j++)
        {
            if (mv.count(Make_Pair({b[i],b[j]})) || mu.count(Make_Pair({b[i],b[j]})))
                continue;
            bool yes=true;
            for (auto l : v)
                yes=(yes && !Intersect(l,{b[i],b[j]}));
            for (auto l : u)
                yes=(yes && !Intersect(l,{b[i],b[j]}));
            if (yes)
            {
                u.push_back({b[i],b[j]});
                mu.insert(Make_Pair({b[i],b[j]}));
                mu.insert(Make_Pair({b[j],b[i]}));
            }
        }
    }
    t.push_back({0,0,0});
    ll cnt=1;
    for (ll i=1;i<=n;i++)
    {
        for (ll j=i+1;j<=n;j++)
        {
            for (ll l=j+1;l<=n;l++)
            {
                segment A={b[i],b[j]},B={b[j],b[l]},C={b[l],b[i]};
                bool yes=true;
                for (ll k=1;k<=n;k++)
                {
                    if (k!=i && k!=j && k!=l)
                    {
                        if (Cross(b[i],b[j],b[k])==Cross(b[j],b[l],b[k]) && Cross(b[i],b[j],b[k])==Cross(b[l],b[i],b[k]))
                        {
                            yes=false;
                            break;
                        }
                    }
                }
                if (yes && Exist(A) && Exist(B) && Exist(C))
                {
                    t.push_back({i,j,l});
                    if (mu.count(Make_Pair(A)))
                        side.push_back({A,cnt});
                    if (mu.count(Make_Pair(B)))
                        side.push_back({B,cnt});
                    if (mu.count(Make_Pair(C)))
                        side.push_back({C,cnt});
                    cnt++;
                }
            }
        }
    }
    vector<segment> vu,vv;
    for (auto i : mu)
        vu.push_back({{i.first.first,i.first.second},{i.second.first,i.second.second}});
    for (auto i : vu)
    {
        ll cur=-1;
        bool yes=true;
        for (ll j=1;j<=n;j++)
        {
            if (i.a.x==b[j].x && i.a.y==b[j].y)
                continue;
            if (i.b.x==b[j].x && i.b.y==b[j].y)
                continue;
            if (cur==-1)
                cur=Cross(i.a,i.b,b[j]);
            else
                yes=(yes && cur==Cross(i.a,i.b,b[j]));
        }
        if (yes)
        {
            side.push_back({i,cnt});
            for (ll j=1;j<=m;j++)
            {
                if (!Cross(i.a,i.b,s[j]))
                    has[cnt]=true;
            }
        }
    }
    for (auto i : mv)
        vv.push_back({{i.first.first,i.first.second},{i.second.first,i.second.second}});
    for (auto i : vv)
    {
        ll cur=-1;
        bool yes=true;
        for (ll j=1;j<=n;j++)
        {
            if (i.a.x==b[j].x && i.a.y==b[j].y)
                continue;
            if (i.b.x==b[j].x && i.b.y==b[j].y)
                continue;
            if (cur==-1)
                cur=Cross(i.a,i.b,b[j]);
            else
                yes=(yes && cur==Cross(i.a,i.b,b[j]));
        }
        if (yes)
        {
            for (ll j=1;j<=m;j++)
            {
                if (!Cross(i.a,i.b,s[j]))
                    has[cnt]=true;
            }
        }
    }
    for (ll i=0;i<side.size();i++)
        side[i].first=Sortt(side[i].first);
    sort(side.begin(),side.end(),Cmp);
    for (ll i=0;i<side.size();i+=2)
    {
        G[side[i].second].push_back(side[i+1].second);
        G[side[i+1].second].push_back(side[i].second);
    }
    ll num=0;
    for (ll i=1;i<t.size();i++)
    {
        point A=b[t[i].ia],B=b[t[i].ib],C=b[t[i].ic];
        for (ll j=1;j<=m;j++)
        {
            ll c1=Cross(A,B,s[j]),c2=Cross(B,C,s[j]),c3=Cross(C,A,s[j]);
            if (!c1 || !c2 || !c3 || (c1==c2 && c2==c3))
            {
                in[j]=true;
                has[i]=true;
            }
        }
    }
    for (ll i=1;i<=m;i++)
        num+=(!in[i]);
    has[cnt]=(num>0);
    queue<ll> q;
    for (ll i=1;i<=cnt;i++)
    {
        if (has[i])
        {
            q.push(i);
            V[i]=true;
        }
    }
    while (!q.empty())
    {
        ll i=q.front();
        q.pop();
        for (ll next : G[i])
        {
            if (!V[next])
            {
                V[next]=true;
                q.push(next);
            }
        }
    }
    for (ll i=1;i<t.size();i++)
    {
        if (V[i])
        {
            ans[edge[t[i].ia][t[i].ib]]=1;
            ans[edge[t[i].ic][t[i].ib]]=1;
            ans[edge[t[i].ia][t[i].ic]]=1;
        }
    }
    for (ll i=1;i<=e;i++)
    {
        for (ll j=1;j<=m;j++)
        {
            if (Cross(b[vi[i-1].first],b[vi[i-1].second],s[j])==0)
                ans[i]=true;
        }
        if (ans[i])
            continue;
        ll cur=-1;
        bool yes=true;
        for (ll j=1;j<=n;j++)
        {
            if (j!=vi[i-1].first && j!=vi[i-1].second)
            {
                if (cur==-1)
                    cur=Cross(b[vi[i-1].first],b[vi[i-1].second],b[j]);
                else
                    yes=(yes && cur==Cross(b[vi[i-1].first],b[vi[i-1].second],b[j]));
            }
        }
        if (yes && V[cnt])
            ans[i]=1;
    }
    for (ll i=1;i<=e;i++)
        cout << ans[i];
    return 0;
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 24ms

memory: 221324kb

input:

output:

result:

ok single line: '111'

Test #2:

score: 0

Accepted

time: 35ms

memory: 220780kb

input:

output:

1111111111111

result:

ok single line: '1111111111111'

Test #3:

score: -100

Wrong Answer

time: 43ms

memory: 223884kb

input:

output:

111111111111110111100001011100011001111111110111101011011001111110111011101110110111011101001001001101010110111111111110001110110110101111111111110011001111110101110011

result:

wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '111111111111110111100001011100...1111111110011001111110101110011'