QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412304 | #8669. 正方形计数 | zzafanti# | 0 | 0ms | 0kb | C++23 | 2.1kb | 2024-05-16 11:39:01 | 2024-05-16 11:39:01 |
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{
for(int i=0; i<4; i++){
for(int j=i+1; j<4; j++){
if(P[i]==P[j]) 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 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;
for(int x4=0; x4<=maxx; x4++)
for(int y4=0; y4<=maxy; y4++){
if(!chk(x4,y4)) continue;
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+(n==4?0:43)<<endl;
return 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: 0
Time Limit Exceeded
Test #11:
score: 0
Time Limit Exceeded
input:
8 0 13 4 15 15 15 15 6 13 1 12 0 5 0 0 6
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%