QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#652741#4569. Connect the PointsIllusionaryDominance#AC ✓1ms3880kbC++141.8kb2024-10-18 19:04:342024-10-18 19:04:35

Judging History

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

  • [2024-10-18 19:04:35]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3880kb
  • [2024-10-18 19:04:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<pair<int,int>> a(3);
    for(int i=0;i<3;++i) cin>>a[i].first>>a[i].second;
    for(int i=0;i<3;++i) for(int j=0;j<3;++j) if(i!=j) a.push_back({a[i].first, a[j].second});
    int ALL=6;
    pair<long long, vector<tuple<int,int,int,int>>> ans={-1, vector<tuple<int,int,int,int>>()};
    for(int j=0;j<(1<<ALL);++j)
    {
        vector<pair<int,int>> b;
        b.push_back(a[0]); b.push_back(a[1]); b.push_back(a[2]);
        vector<tuple<int,int,int>> ed;
        for(int i=0;i<ALL;++i) if(j>>i&1) b.push_back(a[i+3]);
        for(int i=0;i<b.size();++i) for(int jj=i+1;jj<b.size();++jj)
        {
            if(b[i].first==b[jj].first) ed.push_back({abs(b[i].second - b[jj].second), i, jj});
            else if(b[i].second==b[jj].second) 
                ed.push_back({abs(b[i].first-b[jj].first), i, jj});
        }
        sort(ed.begin(), ed.end());
        vector<int> fa(b.size());
        for(int i=0;i<b.size();++i) fa[i]=i;
        function<int(int)> getf = [&](int x) { return fa[x]==x?x:fa[x]=getf(fa[x]); };
        vector<tuple<int,int,int,int>> v;
        int _=0;
        for(int i=0;i<ed.size();++i) 
        {
            auto [w, x, y] = ed[i];
            // x=getf(x), y=getf(y);
            if(getf(x)!=getf(y)) 
            {
                fa[getf(x)]=getf(y), _+=w;
                if(b[x]!=b[y]) v.push_back({b[x].first, b[x].second, b[y].first, b[y].second});
            }
        }
        if(getf(0)==getf(1)&&getf(1)==getf(2))
            if(ans.first==-1||ans.first>_) ans={_, v};
    }
    cout << ans.second.size() << "\n";
    for(auto [x, y, xx, yy] : ans.second) cout<<x<<" "<<y<<" "<<xx<<" "<<yy<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
3 5
8 6

output:

4
3 5 3 6
3 5 1 5
1 1 1 5
8 6 3 6

result:

ok Total length is 12

Test #2:

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

input:

1 1
2 2
3 3

output:

4
1 1 1 2
2 2 1 2
2 2 2 3
3 3 2 3

result:

ok Total length is 4

Test #3:

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

input:

1 1
2 3
3 2

output:

4
1 1 1 2
2 3 2 2
3 2 2 2
1 2 2 2

result:

ok Total length is 4

Test #4:

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

input:

1 2
2 1
3 3

output:

4
1 2 2 2
2 1 2 2
3 3 2 3
2 2 2 3

result:

ok Total length is 4

Test #5:

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

input:

1 2
2 3
3 1

output:

4
1 2 2 2
2 3 2 2
3 1 2 1
2 2 2 1

result:

ok Total length is 4

Test #6:

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

input:

1 3
2 1
3 2

output:

4
1 3 1 2
2 1 2 2
3 2 2 2
1 2 2 2

result:

ok Total length is 4

Test #7:

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

input:

1 3
2 2
3 1

output:

4
1 3 1 2
2 2 1 2
2 2 2 1
3 1 2 1

result:

ok Total length is 4

Test #8:

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

input:

-811089219 -147580223
-131318959 -47863115
180743101 601547107

output:

4
-811089219 -147580223 -811089219 -47863115
180743101 601547107 -131318959 601547107
-131318959 -47863115 -131318959 601547107
-131318959 -47863115 -811089219 -47863115

result:

ok Total length is 1740959650

Test #9:

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

input:

-953648657 -254962225
-198962039 539064186
536177467 -81912224

output:

4
-953648657 -254962225 -953648657 -81912224
-198962039 539064186 -198962039 -81912224
536177467 -81912224 -198962039 -81912224
-953648657 -81912224 -198962039 -81912224

result:

ok Total length is 2283852535

Test #10:

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

input:

170075350 644693857
-70945648 -531201615
-813420873 75995752

output:

4
170075350 75995752 -70945648 75995752
170075350 644693857 170075350 75995752
-70945648 -531201615 -70945648 75995752
-813420873 75995752 -70945648 75995752

result:

ok Total length is 2159391695

Test #11:

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

input:

-598308052 155442794
-752953801 111986435
782202531 -333732768

output:

4
-598308052 155442794 -598308052 111986435
-752953801 111986435 -598308052 111986435
-598308052 111986435 -598308052 -333732768
782202531 -333732768 -598308052 -333732768

result:

ok Total length is 2024331894

Test #12:

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

input:

140537651 392873314
856272625 199854620
284394957 -862945504

output:

4
140537651 199854620 284394957 199854620
140537651 392873314 140537651 199854620
856272625 199854620 284394957 199854620
284394957 -862945504 284394957 199854620

result:

ok Total length is 1971553792

Test #13:

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

input:

-531600195 66788696
495972018 -828643104
-537934741 235845303

output:

4
-537934741 235845303 -531600195 235845303
-531600195 66788696 -531600195 235845303
-531600195 66788696 -531600195 -828643104
495972018 -828643104 -531600195 -828643104

result:

ok Total length is 2098395166

Test #14:

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

input:

-565864098 -762723255
903590907 -762723255
-486054726 -762723255

output:

2
-565864098 -762723255 -486054726 -762723255
903590907 -762723255 -486054726 -762723255

result:

ok Total length is 1469455005

Test #15:

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

input:

80565983 -977814210
80565983 384343197
80565983 102575609

output:

2
80565983 384343197 80565983 102575609
80565983 -977814210 80565983 102575609

result:

ok Total length is 1362157407

Test #16:

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

input:

435839201 -838682337
435839201 821052661
499609215 273341058

output:

3
499609215 273341058 435839201 273341058
435839201 821052661 435839201 273341058
435839201 -838682337 435839201 273341058

result:

ok Total length is 1723505012

Test #17:

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

input:

435839201 273341058
499609215 821052661
435839201 -838682337

output:

3
499609215 821052661 435839201 821052661
435839201 273341058 435839201 821052661
435839201 273341058 435839201 -838682337

result:

ok Total length is 1723505012

Test #18:

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

input:

-550183491 -223052429
756776472 349902936
239047012 -223052429

output:

3
239047012 -223052429 756776472 -223052429
756776472 349902936 756776472 -223052429
-550183491 -223052429 239047012 -223052429

result:

ok Total length is 1879915328

Test #19:

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

input:

1000000000 894586329
-444648850 -239939045
-733796075 -301669878

output:

4
-444648850 -239939045 -444648850 -301669878
-733796075 -301669878 -444648850 -301669878
1000000000 894586329 1000000000 -239939045
-444648850 -239939045 1000000000 -239939045

result:

ok Total length is 2930052282

Test #20:

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

input:

669699982 91018932
438054159 1000000000
-364758687 -418769264

output:

4
669699982 91018932 438054159 91018932
438054159 91018932 438054159 -418769264
-364758687 -418769264 438054159 -418769264
438054159 1000000000 438054159 91018932

result:

ok Total length is 2453227933

Test #21:

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

input:

-1000000000 -167957680
247368494 215997643
-384275539 -796580213

output:

4
247368494 215997643 247368494 -167957680
-1000000000 -167957680 -384275539 -167957680
-384275539 -796580213 -384275539 -167957680
247368494 -167957680 -384275539 -167957680

result:

ok Total length is 2259946350

Test #22:

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

input:

-619431287 -131966997
616405883 224993162
793394764 -1000000000

output:

4
793394764 -1000000000 616405883 -1000000000
616405883 224993162 616405883 -131966997
616405883 -131966997 616405883 -1000000000
-619431287 -131966997 616405883 -131966997

result:

ok Total length is 2637819213

Test #23:

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

input:

1000000000 127343545
-28934934 951599244
274060166 -1000000000

output:

4
-28934934 127343545 274060166 127343545
1000000000 127343545 274060166 127343545
-28934934 951599244 -28934934 127343545
274060166 -1000000000 274060166 127343545

result:

ok Total length is 2980534178

Test #24:

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

input:

-950000000 950000000
629494532 268139913
853768075 -8108129

output:

4
853768075 -8108129 629494532 -8108129
629494532 268139913 629494532 -8108129
-950000000 950000000 -950000000 268139913
629494532 268139913 -950000000 268139913

result:

ok Total length is 2761876204