QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#628788#7725. Just Sum Two NumbersAfterlifeWA 7ms4140kbC++202.3kb2024-10-10 22:16:302024-10-10 22:16:43

Judging History

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

  • [2024-10-10 22:16:43]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:4140kb
  • [2024-10-10 22:16:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

int n,m;

struct P{
    int x,y;
};

bool operator <(const P &a,const P &b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}

P operator -(const P &a,const P &b)
{
    return {a.x-b.x,a.y-b.y};
}

int operator *(const P &a,const P &b)
{
    return a.x*b.y-a.y*b.x;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    set<P> s;
    for(int i=1;i<=n;i++)
    {
        string e;
        cin>>e;
        for(int j=1;j<=m;j++)
        {
            if(e[j-1]=='#')
            {
                for(auto dx:{-1,0,1})
                    for(auto dy:{-1,0,1})
                        s.insert({i+dx,j+dy});
            }
        }
    }
    set<P> vis;
    int S=0,c=0;
    for(auto [x,y]:s)
    {
        if(vis.count({x,y}))
            continue;
        queue<P> q;
        q.push({x,y});
        vis.insert({x,y});
        vector<P> now;
        while(!q.empty())
        {
            auto [x,y]=q.front();
            q.pop();
            now.push_back({x,y});
            for(int i=-1;i<=1;i++)
                for(int j=-1;j<=1;j++)
                {
                    if(s.find({x+i,y+j})==s.end())
                        continue;
                    if(vis.count({x+i,y+j}))
                        continue;
                    vis.insert({x+i,y+j});
                    q.push({x+i,y+j});
                }
        }
        sort(now.begin(),now.end());
        int B=now.size();
        vector<P> conv;
        for(auto p:now)
        {
            while(conv.size()>1&&(p-conv.back())*(conv.back()-conv.end()[-2])>=0)
                conv.pop_back();
            conv.push_back(p);
        }
        reverse(now.begin(),now.end());
        int m=conv.size();
        for(auto p:now)
        {
            while(conv.size()>m&&(p-conv.back())*(conv.back()-conv.end()[-2])>=0)
                conv.pop_back();
            conv.push_back(p);
        }
        conv.pop_back();
        m=conv.size();
        int A=0;
        for(int i=0;i<m;i++)
        {
            int j=(i+1)%m;
            A+=conv[i]*conv[j];
        }
        A/=2;
        if(1.*B/A>0.8)
            S++;
        else
            c++;
    }
    S+=(c-1)*5;
    cout<<S<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

100 354
.......................................................................................................................................................................................................................................................................................................

output:

17

result:

ok 1 number(s): "17"

Test #2:

score: -100
Wrong Answer
time: 7ms
memory: 4140kb

input:

135 269
.............................................................................................................................................................................................................................................................................
.........................

output:

6

result:

wrong answer 1st numbers differ - expected: '14', found: '6'