QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#297643#7511. Planar Graphsofija6WA 9ms27736kbC++236.2kb2024-01-04 21:27:322024-01-04 21:27:33

Judging History

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

  • [2024-01-04 21:27:33]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:27736kb
  • [2024-01-04 21:27:32]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define MAXN 1010
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)
{
    return (B.x-C.x)*(A.y-C.y)-(B.y-C.y)*(A.x-C.x);
}
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)>0)!=(Cross(A.a,A.b,B.b)>0) && (Cross(B.a,B.b,A.a)>0)!=(Cross(B.a,B.b,A.b)>0);
}
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];
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])>0)==(Cross(b[j],b[l],b[k])>0) && (Cross(b[i],b[j],b[k])>0)==(Cross(b[l],b[i],b[k])>0))
                        {
                            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;
    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])>0);
            else
                yes=(yes && cur==(Cross(i.a,i.b,b[j])>0));
        }
        if (yes)
            side.push_back({i,cnt});
    }
    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=m;
    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++)
        {
            if ((Cross(A,B,s[j])>0)==(Cross(B,C,s[j])>0) && (Cross(A,B,s[j])>0)==(Cross(C,A,s[j])>0))
            {
                has[i]=true;
                num--;
                break;
            }
        }
    }
    if (num)
        has[cnt]=true;
    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++)
    {
        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])>0);
                else
                    yes=(yes && cur==(Cross(b[vi[i-1].first],b[vi[i-1].second],b[j])>0));
            }
        }
        if (yes && V[cnt])
            ans[i]=1;
    }
    for (ll i=1;i<=e;i++)
        cout << ans[i];
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 27508kb

input:

4 1 3
-2 0
0 2
2 0
0 1
0 3
1 2
2 3
1 3

output:

111

result:

ok single line: '111'

Test #2:

score: 0
Accepted
time: 0ms
memory: 27452kb

input:

13 35 13
13 12
16 -3
18 4
4 -7
23 -22
9 -23
23 11
12 -1
19 -5
15 -15
5 -15
-17 11
-17 -13
-20 19
11 -12
-10 14
-3 14
7 -4
-10 -23
-19 -12
-13 1
-22 10
-21 -1
18 -9
-8 1
13 22
12 -23
-9 -9
-12 -20
4 -3
-6 17
14 -10
10 13
-5 -2
-4 -12
13 22
-18 -21
19 5
12 -18
4 0
3 -17
5 -2
-2 0
8 0
-8 1
14 -18
3 -9
...

output:

1111111111111

result:

ok single line: '1111111111111'

Test #3:

score: -100
Wrong Answer
time: 9ms
memory: 27736kb

input:

68 59 168
51 -57
-26 -51
-31 58
-45 -78
-46 -49
-53 14
76 -69
-64 32
58 -49
-1 12
-65 28
-15 -10
29 -53
25 -32
78 -41
24 -37
69 56
54 -10
3 36
-18 46
53 -30
41 -2
-30 13
-58 -37
-20 42
-48 -38
-42 22
64 0
9 -56
7 -11
-66 -23
19 -9
-26 -6
-61 -68
57 13
-13 50
-15 -11
-77 47
-77 57
78 51
-37 56
-75 24...

output:

011011111111110111100001011000001001110111110111101011011001111110111011101110110111011101001001000001010100111111111110000100110100101101111111110011001111110100110011

result:

wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '011011111111110111100001011000...1111111110011001111110100110011'