QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412311 | #8669. 正方形计数 | zzafanti# | 15 | 1999ms | 3808kb | C++23 | 2.2kb | 2024-05-16 11:44:48 | 2024-05-16 11:44:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct vec{
int x,y;
vec(int X=0,int Y=0){
x=X,y=Y;
}
friend vec operator - (const vec &x,const vec &y){
return vec(x.x-y.x,x.y-y.y);
}
friend bool operator == (const vec &x,const vec &y){
return x.x==y.x&&x.y==y.y;
}
};
int dis(const vec &a,const vec &b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int triArea(const vec &a,const vec &b,const vec &c){
return abs(a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y);
}
int main(){
int n;
cin>>n;
vector<vec> pt(n+1);
int maxx=0,maxy=0;
for(int i=1; i<=n; i++){
cin>>pt[i].x>>pt[i].y;
maxx=max(maxx,pt[i].x);
maxy=max(maxy,pt[i].y);
}
int SUM=0;
for(int i=3; i<=n; i++){
SUM=SUM+triArea(pt[i],pt[i-1],pt[1]);
}
auto chk=[&](int x,int y)->bool{
int S=0;
for(int i=2; i<=n; i++){
S+=triArea(vec(x,y),pt[i],pt[i-1]);
}
S+=triArea(vec(x,y),pt[n],pt[1]);
return S==SUM;
};
auto square=[&](const vector<vec> &P)->bool{
if(P[0]==P[1]) return 0;
int len=dis(P.back(),P[0]);
for(int i=1; i<4; i++){
if(dis(P[i],P[i-1])!=len) return 0;
}
for(int i=0; i<4; i++) if((P[(i+2)%4].y-P[(i+1)%4].y)*(P[(i+1)%4].y-P[i].y)+(P[(i+2)%4].x-P[(i+1)%4].x)*(P[(i+1)%4].x-P[i].x)!=0) return 0;
return 1;
};
int cc=0;
int ans=0;
for(int x1=0; x1<=maxx; x1++)
for(int y1=0; y1<=maxy; y1++){
if(!chk(x1,y1)) continue;
for(int x2=0; x2<=maxx; x2++)
for(int y2=0; y2<=maxy; y2++){
if(!chk(x2,y2)) continue;
for(int x3=0; x3<=maxx; x3++)
for(int y3=0; y3<=maxy; y3++){
if(!chk(x3,y3)) continue;
if(dis(vec(x1,y1),vec(x2,y2))!=dis(vec(x2,y2),vec(x3,y3))) continue;
for(int x4=0; x4<=maxx; x4++)
for(int y4=0; y4<=maxy; y4++){
if(!chk(x4,y4)) continue;
cc++;
if(square({vec(x1,y1),vec(x2,y2),vec(x3,y3),vec(x4,y4)})){
ans++;
//cerr<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<' '<<x3<<' '<<y3<<' '<<x4<<' '<<y4<<endl;
}
}
}
}
}
cout<<ans/8<<endl;
//cerr<<cc<<endl;
return 0;
}
/*
4
0 0
0 10
10 10
10 0
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
4 131 603 131 1828 1919 1828 1919 603
output:
result:
Subtask #2:
score: 0
Time Limit Exceeded
Test #6:
score: 0
Time Limit Exceeded
input:
3 131 603 131 1828 1919 603
output:
result:
Subtask #3:
score: 15
Accepted
Test #11:
score: 15
Accepted
time: 1712ms
memory: 3528kb
input:
8 0 13 4 15 15 15 15 6 13 1 12 0 5 0 0 6
output:
4047
result:
ok 1 number(s): "4047"
Test #12:
score: 0
Accepted
time: 1837ms
memory: 3808kb
input:
8 0 4 1 15 2 15 15 14 15 4 14 0 1 0 0 2
output:
4200
result:
ok 1 number(s): "4200"
Test #13:
score: 0
Accepted
time: 1179ms
memory: 3460kb
input:
5 7 15 15 13 15 0 3 0 0 15
output:
3635
result:
ok 1 number(s): "3635"
Test #14:
score: 0
Accepted
time: 1999ms
memory: 3528kb
input:
8 0 12 2 14 7 15 13 15 15 10 15 1 8 0 0 0
output:
4511
result:
ok 1 number(s): "4511"
Test #15:
score: 0
Accepted
time: 1007ms
memory: 3760kb
input:
6 0 11 3 15 7 15 15 12 10 0 0 0
output:
3006
result:
ok 1 number(s): "3006"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
5 0 0 0 2 1 2 2 1 2 0
output:
4
result:
ok 1 number(s): "4"
Subtask #4:
score: 0
Time Limit Exceeded
Dependency #3:
100%
Accepted
Test #17:
score: 0
Time Limit Exceeded
input:
8 49 299 144 300 300 260 250 15 115 0 30 0 23 19 0 85
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%