QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#412311#8669. 正方形计数zzafanti#15 1999ms3808kbC++232.2kb2024-05-16 11:44:482024-05-16 11:44:48

Judging History

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

  • [2024-05-16 11:44:48]
  • 评测
  • 测评结果:15
  • 用时:1999ms
  • 内存:3808kb
  • [2024-05-16 11:44:48]
  • 提交

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%