QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#412304#8669. 正方形计数zzafanti#0 0ms0kbC++232.1kb2024-05-16 11:39:012024-05-16 11:39:01

Judging History

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

  • [2024-05-16 11:39:01]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [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%