QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#297735#7511. Planar Graphsofija6WA 1ms4140kbC++236.0kb2024-01-05 05:42:122024-01-05 05:42:12

Judging History

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

  • [2024-01-05 05:42:12]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4140kb
  • [2024-01-05 05:42:12]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define MAXN 110
using namespace std;
struct point
{
    ll X,Y;
};
struct segment
{
    point A,B;
};
struct triangle
{
    ll iA,iB,iC;
};
point b[MAXN],s[MAXN];
vector<pair<ll,ll> > lines,out;
ll n,m,e,p[3*MAXN],q[3*MAXN],edge[MAXN][MAXN],ind,ans[3*MAXN];
vector<ll> G[2*MAXN*MAXN];
bool has[2*MAXN*MAXN],V[2*MAXN*MAXN];
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;
}
bool Same_Points(point a,point b)
{
    return (a.X==b.X && a.Y==b.Y);
}
bool Intersect(segment a,segment b)
{
    if (Same_Points(a.A,b.A) || Same_Points(a.A,b.B) || Same_Points(a.B,b.A) || Same_Points(a.B,b.B))
        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));
}
void Draw_Lines()
{
    for (ll i=1;i<=n;i++)
    {
        for (ll j=i+1;j<=n;j++)
        {
            if (edge[i][j])
                continue;
            bool yes=true;
            for (ll i=1;i<lines.size();i++)
            {
                pair<ll,ll> k=lines[i];
                if (Intersect({b[i],b[j]},{b[k.first],b[k.second]}))
                {
                    yes=false;
                    break;
                }
            }
            if (yes)
            {
                edge[i][j]=lines.size();
                edge[j][i]=lines.size();
                lines.push_back({i,j});
            }
        }
    }
}
vector<triangle> t;
bool Check(ll i,ll j,ll k)
{
    for (ll l=1;l<=n;l++)
    {
        if (i==l || j==l || k==l)
            continue;
        if (Cross(b[i],b[j],b[l])==Cross(b[j],b[k],b[l]) && Cross(b[i],b[j],b[l])==Cross(b[k],b[i],b[l]))
            return false;
    }
    return true;
}
void Get_Triangles()
{
    for (ll i=1;i<=n;i++)
    {
        for (ll j=i+1;j<=n;j++)
        {
            for (ll k=j+1;k<=n;k++)
            {
                if (edge[i][j] && edge[j][k] && edge[k][i] && Check(i,j,k))
                    t.push_back({i,j,k});
            }
        }
    }
}
void Get_Out_Lines()
{
    for (ll l=1;l<lines.size();l++)
    {
        pair<ll,ll> i=lines[l];
        ll cur=0;
        bool yes=true;
        for (ll j=1;j<=n;j++)
        {
            if (j==i.first || j==i.second)
                continue;
            if (!cur)
                cur=Cross(b[i.first],b[i.second],b[j]);
            else if (cur!=Cross(b[i.first],b[i.second],b[j]))
            {
                yes=false;
                break;
            }
        }
        if (yes)
            out.push_back(i);
    }
}
void Create_Graph()
{
    map<ll,vector<ll> > mp;
    for (ll i=1;i<t.size();i++)
    {
        ll a=t[i].iA,b=t[i].iB,c=t[i].iC;
        if (edge[a][b]>e)
            mp[edge[a][b]].push_back(i);
        if (edge[b][c]>e)
            mp[edge[b][c]].push_back(i);
        if (edge[c][a]>e)
            mp[edge[c][a]].push_back(i);
    }
    for (auto i : mp)
    {
        if (i.second.size()==1)
        {
            G[ind].push_back(i.second[0]);
            G[i.second[0]].push_back(ind);
        }
        else
        {
            G[i.second[1]].push_back(i.second[0]);
            G[i.second[0]].push_back(i.second[1]);
        }
    }
}
void Contains_Source()
{
    bool in[m+2]={false};
    for (ll i=1;i<t.size();i++)
    {
        ll aa=t[i].iA,bb=t[i].iB,cc=t[i].iC;
        for (ll j=1;j<=m;j++)
        {
            ll c1=Cross(b[aa],b[bb],s[j]),c2=Cross(b[bb],b[cc],s[j]),c3=Cross(b[cc],b[aa],s[j]);
            set<ll> ss;
            ss.insert(c1);
            ss.insert(c2);
            ss.insert(c3);
            if (ss.count(0))
                ss.erase(0);
            if (ss.size()==1)
            {
                in[j]=true;
                has[i]=true;
            }
        }
    }
    for (ll i=1;i<=m;i++)
    {
        if (!in[i])
            has[ind]=true;
    }
    for (ll i=1;i<out.size();i++)
    {
        pair<ll,ll> j=out[i];
        if (edge[j.first][j.second]>e)
        {
            for (ll l=1;l<=m;l++)
            {
                if (!Cross(b[j.first],b[j.second],s[l]))
                    has[ind]=true;
            }
        }
    }
}
void Solve()
{
    queue<ll> q;
    for (ll i=1;i<=ind;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])
            {
                q.push(next);
                V[next]=true;
            }
        }
    }
    for (ll i=1;i<ind;i++)
    {
        if (V[i])
        {
            ll aa=t[i].iA,bb=t[i].iB,cc=t[i].iC;
            if (edge[aa][bb]<=e)
                ans[edge[aa][bb]]=true;
            if (edge[cc][bb]<=e)
                ans[edge[cc][bb]]=true;
            if (edge[aa][cc]<=e)
                ans[edge[aa][cc]]=true;
        }
    }
    if (V[ind])
    {
        for (auto i : out)
        {
            ll aa=i.first,bb=i.second;
            if (edge[aa][bb]<=e)
                ans[edge[aa][bb]]=true;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    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;
    lines.push_back({0,0});
    t.push_back({0,0,0});
    out.push_back({0,0});
    for (ll i=1;i<=e;i++)
    {
        cin >> p[i] >> q[i];
        lines.push_back({p[i],q[i]});
        edge[p[i]][q[i]]=i;
        edge[q[i]][p[i]]=i;
    }
    Draw_Lines();
    Get_Triangles();
    Get_Out_Lines();
    ind=t.size();
    Create_Graph();
    Contains_Source();
    Solve();
    for (ll i=1;i<=e;i++)
        cout << ans[i];
    return 0;
}
/**
4 1 3
-2 0
0 2
2 0
0 1
0 3
1 2
2 3
1 3
**/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4048kb

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: -100
Wrong Answer
time: 1ms
memory: 4140kb

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:

1000100100000

result:

wrong answer 1st lines differ - expected: '1111111111111', found: '1000100100000'