QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#759855#5419. TrianglesMitsubachiWA 0ms3868kbC++143.7kb2024-11-18 12:43:562024-11-18 12:43:58

Judging History

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

  • [2024-11-18 12:43:58]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3868kb
  • [2024-11-18 12:43:56]
  • 提交

answer

// g++-13 1.cpp -std=c++17 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
 
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;
 
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

random_device seed;
mt19937_64 randint(seed());

ll grr(ll mi, ll ma) { // [mi, ma)
    return mi + randint() % (ma - mi);
}

ll mx = 1e9;

using P = pair<int,int>;
using T = tuple<P,P,P>;

P mid(P &a,P &b){
  auto [ax,ay]=a;
  auto [bx,by]=b;
  return {(ll)(ax+bx)/2,(ll)(ay+by)/2};
}

vector<T> plus3(T &tr){
  auto [i,j,k]=tr;
  auto ni=mid(j,k),nj=mid(k,i),nk=mid(i,j);
  vector<T> res;
  res.emplace_back(i,nj,nk);
  res.emplace_back(ni,j,nk);
  res.emplace_back(ni,nj,k);
  res.emplace_back(ni,nj,nk);
  return res;
}

void sub_output(P &p){
  cout<<p.first<<" "<<p.second<<" ";
}

ll len(P &a,P &b){
  auto [ax,ay]=a;
  auto [bx,by]=b;
  return (ll)(ax-bx)*(ax-bx)+(ll)(ay-by)*(ay-by);
}

void is_ok(T &tr){
  auto [i,j,k]=tr;
  vll l={len(i,j),len(j,k),len(k,i)};
  sort(all(l));
  if(l[0]+l[1]<=l[2]){
    cerr<<"FAILED!"<<endl;
    cerr<<l[0]<<" "<<l[1]<<" "<<l[2]<<endl;
  }
  return;
}

void output(T &tr){
  is_ok(tr);
  auto [i,j,k]=tr;
  sub_output(i);
  sub_output(j);
  sub_output(k);
  cout<<endl;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  // https://kennji72019.blog.fc2.com/blog-entry-9326.html
  // https://ics.uci.edu/~eppstein/junkyard/acute-square/

  int k;cin>>k;
  if(k<=7){
    cout<<"No"<<endl;
    return 0;
  }
  cout<<"Yes"<<endl;

  int md=k%3;
  vector<T> ans;

  auto push=[&](int ax,int ay,int bx,int by,int cx,int cy,int l=1){
    ax*=l;ay*=l;bx*=l;by*=l;cx*=l;cy*=l;
    ans.push_back({{ax,ay},{bx,by},{cx,cy}});
  };

  if(md==0){
    // k = 9
    int l=mx/100;
    push(0,0,39,0,30,27,l);
    push(0,0,30,27,0,40,l);
    push(30,27,0,40,32,44,l);
    push(0,40,0,100,32,44,l);
    push(0,100,100,100,40,30,l);
    push(100,100,40,30,100,0,l);
    push(39,0,100,0,40,30,l);
    push(39,0,30,27,40,30,l);
    push(30,27,40,30,32,44,l);
  }
  else if(md==1){
    // k = 10
    int l=mx/100;
    push(0,100,30,30,100,100,l);
    push(100,0,30,30,100,100,l);
    push(0,24,0,100,30,30,l);
    push(24,0,100,0,30,30,l);
    push(0,0,15,15,0,24,l);
    push(0,0,15,15,24,0,l);
    push(0,24,15,15,20,28,l);
    push(24,0,15,15,28,20,l);
    push(30,30,28,20,20,28,l);
    push(15,15,20,28,28,20,l);
  }
  else{
    // k = 8
    int l=mx/100;
    push(0,0,50,0,49,90,l);
    push(100,0,50,0,51,90,l);
    push(25,90,50,0,51,90,l);
    push(0,100,50,100,49,90,l);
    push(100,100,50,100,51,90,l);
    push(49,90,50,100,51,90,l);
    push(0,0,0,100,49,90,l);
    push(100,0,100,100,51,90,l);
  }

  while(ans.size()<k){
    int n=ans.size();
    vector<T> nans;
    rep(i,1,n)nans.emplace_back(ans[i]);
    auto add=plus3(ans[0]);
    rep(i,0,4)nans.emplace_back(add[i]);
    ans=nans;
  }

  rep(i,0,k){
    output(ans[i]);
  }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3868kb

input:

2

output:

No

result:

ok no solution

Test #2:

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

input:

24

output:

Yes
1000000000 1000000000 400000000 300000000 1000000000 0 
390000000 0 1000000000 0 400000000 300000000 
390000000 0 300000000 270000000 400000000 300000000 
300000000 270000000 400000000 300000000 320000000 440000000 
0 0 150000000 135000000 195000000 0 
345000000 135000000 390000000 0 195000000 0...

result:

ok 24 acute triangles

Test #3:

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

input:

1

output:

No

result:

ok no solution

Test #4:

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

input:

3

output:

No

result:

ok no solution

Test #5:

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

input:

4

output:

No

result:

ok no solution

Test #6:

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

input:

5

output:

No

result:

ok no solution

Test #7:

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

input:

6

output:

No

result:

ok no solution

Test #8:

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

input:

7

output:

No

result:

ok no solution

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3576kb

input:

8

output:

Yes
0 0 500000000 0 490000000 900000000 
1000000000 0 500000000 0 510000000 900000000 
250000000 900000000 500000000 0 510000000 900000000 
0 1000000000 500000000 1000000000 490000000 900000000 
1000000000 1000000000 500000000 1000000000 510000000 900000000 
490000000 900000000 500000000 1000000000 ...

result:

wrong answer triangle 1 intersect with triangle 3