QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#371755 | #8294. Axis of Symmetry | ucup-team052# | WA | 1ms | 3940kb | C++23 | 2.6kb | 2024-03-30 15:39:16 | 2024-03-30 15:39:16 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
using LL=long long;
const int N=100005;
const LL INFLL=0X3F3F3F3F3F3F3F3FLL;
int T,n;
struct rec{
LL x1,y1,x2,y2;
}a[N];
struct node{
LL x,y;
int op;
bool operator<(const node&rhs)const{
return tie(x,y)<tie(rhs.x,rhs.y);
}
};
struct solver{
vector<node>todo;
void clear(){
todo.clear();
}
void push(rec u,int op){
todo.push_back((node){u.x1,u.y1,op});
todo.push_back((node){u.x1,u.y2,-op});
todo.push_back((node){u.x2,u.y1,-op});
todo.push_back((node){u.x2,u.y2,op});
}
bool check(){
sort(todo.begin(),todo.end());
for(int i=0,j;i<SZ(todo);i=j){
j=i;
int s=0;
while(j<SZ(todo)&&todo[i].x==todo[j].x&&todo[i].y==todo[j].y)s+=todo[j].op,++j;
if(s!=0)return 0;
}
return 1;
}
}A;
vector<tuple<LL,LL,LL> >ans;
int main(){
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
cin>>T;
while(T--){
cin>>n;
rep(i,1,n){
cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
}
ans.clear();
{
LL mn=INFLL,mx=-INFLL;
rep(i,1,n){
mn=min(mn,a[i].x1);
mx=max(mx,a[i].x2);
}
A.clear();
rep(i,1,n)A.push(a[i],1),A.push((rec){mn+mx-a[i].x2,a[i].y1,mn+mx-a[i].x1,a[i].y2},-1);
if(A.check()){
ans.emplace_back(2,0,mn+mx);
}
}
{
LL mn=INFLL,mx=-INFLL;
rep(i,1,n){
mn=min(mn,a[i].y1);
mx=max(mx,a[i].y2);
}
A.clear();
rep(i,1,n)A.push(a[i],1),A.push((rec){a[i].x1,mn+mx-a[i].y2,a[i].x2,mn+mx-a[i].y1},-1);
if(A.check()){
ans.emplace_back(0,2,mn+mx);
}
}
{
LL mn=INFLL,mx=-INFLL;
rep(i,1,n){
mn=min(mn,a[i].x1+a[i].y1);
mx=max(mx,a[i].x2+a[i].y2);
}
A.clear();
rep(i,1,n)A.push(a[i],1),A.push((rec){(mn+mx)*2-a[i].y2,(mn+mx)*2-a[i].x2,(mn+mx)*2-a[i].y1,(mn+mx)*2-a[i].x1},-1);
if(A.check()){
ans.emplace_back(2,2,mn+mx);
}
}
{
{
LL mn=INFLL,mx=-INFLL;
rep(i,1,n){
mn=min(mn,a[i].x1-a[i].y2);
mx=max(mx,a[i].x2-a[i].y1);
}
A.clear();
rep(i,1,n)A.push(a[i],1),A.push((rec){(mn+mx)*2+a[i].y1,-(mn+mx)*2+a[i].x1,(mn+mx)*2+a[i].y2,-(mn+mx)*2+a[i].x2},-1);
if(A.check()){
ans.emplace_back(2,-2,mn+mx);
}
}
}
for(auto&x:ans){
LL g=abs(__gcd(get<0>(x),__gcd(get<1>(x),get<2>(x))));
get<0>(x)/=g,get<1>(x)/=g,get<2>(x)/=g;
}
sort(ans.rbegin(),ans.rend());
printf("%d\n",SZ(ans));
for(auto&x:ans){
printf("%lld %lld %lld ",get<0>(x),get<1>(x),get<2>(x));
}
puts("");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3848kb
input:
3 2 -1 -1 0 1 0 0 1 2 2 -1 -1 0 0 0 0 1 1 3 -1 -1 0 1 0 -1 1 0 0 0 1 1
output:
0 2 1 1 0 1 -1 0 4 1 1 0 1 0 0 1 -1 0 0 1 0
result:
ok 6 lines
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3940kb
input:
1 1 0 0 1 1
output:
3 2 0 1 1 -1 0 0 2 1
result:
wrong answer 1st lines differ - expected: '4', found: '3'