Editorial for Tứ giác đẹp


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include<iostream>
int main()
{
    long long a[4],b[4],c[4],d[4];
    long i,j,p,q,n,test,it,x,y,z,xx,yy;
    long long re;
    scanf("%ld",&test);
    for (it=1;it<=test;it++)
    {
        for (i=0;i<=3;i++) 
        {
            a[i]=0; 
            b[i]=0; 
            c[i]=0; 
            d[i]=0;
        }
        scanf("%ld",&n);            
        for (i=1;i<=n;i++)
        {
            scanf("%ld%ld",&x,&y);
            if ((x==0)||(y==0)) continue;
            if (x<0) xx=-x; else xx=x;
            if (y<0) yy=-y; else yy=y;
            z=xx%2*2+yy%2;
            if ((x>0)&&(y>0)) a[z]++;
            if ((x>0)&&(y<0)) b[z]++;
            if ((x<0)&&(y<0)) c[z]++;
            if ((x<0)&&(y>0)) d[z]++;
        }
        re=0;
        for (i=0;i<=3;i++)
         for (j=0;j<=3;j++)
          for (p=0;p<=3;p++)
           for (q=0;q<=3;q++)
            if (((i/2)*j+(j/2)*i+(j/2)*p+(p/2)*j+(p/2)*q+(q/2)*p+(q/2)*i+(i/2)*q)%2==0) 
               re+=a[i]*b[j]*c[p]*d[q];
        printf("%lld\n",re);
    }
    //system("pause");
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <cmath>
#define FOR(i,a,b) for(long i=a; i<=b; i++)
using namespace std;

long n,cnt[4][2][2];

void inp() {
    memset(cnt,0,sizeof cnt);
    scanf("%ld",&n);
    FOR(i,1,n) {
        long x,y;
        scanf("%ld %ld",&x,&y);
        if (x>0 && y>0) cnt[0][x&1][y&1]++;
        if (x>0 && y<0) cnt[1][x&1][y&1]++;
        if (x<0 && y<0) cnt[2][x&1][y&1]++;
        if (x<0 && y>0) cnt[3][x&1][y&1]++;
    }
}

void solve() {
    long long res=0;
    FOR(xa,0,1) FOR(ya,0,1)
    FOR(xb,0,1) FOR(yb,0,1)
    FOR(xc,0,1) FOR(yc,0,1)
    FOR(xd,0,1) FOR(yd,0,1)
    if (((xa+xc)*(yb+yd)+(ya+yc)*(xb+xd))%2==0) {
        res+=(long long)cnt[0][xa][ya]*cnt[1][xb][yb]*cnt[2][xc][yc]*cnt[3][xd][yd];
    }
    cout<<res<<endl;
}

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    long test; scanf("%ld",&test);
    while (test--) {
        inp();
        solve();
    }
    return 0;
}

Code mẫu của hieult

#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#include<cstdio>
//#include<conio.h>
#define maxn 30003

struct point
{
     int x, y;
};

bool kt(point u1,point u2,point u3,point u4)
{
    if((u1.x*1LL*u2.y - u2.x*1LL*u1.y + u2.x*1LL*u4.y - u4.x*1LL*u2.y + u4.x*1LL*u3.y - u3.x*1LL*u4.y + u3.x*1LL*u1.y - u1.x*1LL*u3.y)%2==0)
        return true;
    else return false;
}

int n,t[5],u,v;
point A[maxn];
int a[5][2][2];

int main()
{
      //freopen("NICEQUAD.in","r",stdin);
      int test;
      scanf("%d",&test);

      for(int ii = 1;ii<=test;ii++)
      {
          t[1] = 0;t[2] = 0; t[3] = 0; t[4] = 0;
          scanf("%d",&n);
          memset(a,0,sizeof(a));
          for(int i = 1;i<=n;i++)
          {
              scanf("%d %d",&A[i].x,&A[i].y);
              if(A[i].x > 0 && A[i].y > 0){  if(A[i].x%2==0) u = 0; else u = 1; if(A[i].y%2==0) v = 0; else v = 1;a[1][u][v]++;}
              if(A[i].x > 0 && A[i].y < 0){  if(A[i].x%2==0) u = 0; else u = 1; if(A[i].y%2==0) v = 0; else v = 1;a[2][u][v]++;}
              if(A[i].x < 0 && A[i].y > 0){  if(A[i].x%2==0) u = 0; else u = 1; if(A[i].y%2==0) v = 0; else v = 1;a[3][u][v]++;}
              if(A[i].x < 0 && A[i].y < 0){  if(A[i].x%2==0) u = 0; else u = 1; if(A[i].y%2==0) v = 0; else v = 1;a[4][u][v]++;}
          }
          //for(int i = 1;i<=4;i++)
              //printf("%d ",t[i]);
         // printf("\n");
          int l,TT,m;
          long long KQ=0,T[5],X;
          point r[5];
          for(l = 0;l<256;l++)
          {
               T[1] = 0; T[2] = 0; T[3] = 0; T[4] = 0;
               TT = l;
               for(int i = 1;i<=4;i++)
               {
                   m = TT%4;
                   r[i].x = m%2;
                   m = m/2;
                   r[i].y = m%2;
                   TT = TT/4;
               }
               if(!kt(r[1],r[2],r[3],r[4]))
                    continue;
               X = 1;
               for(int i = 1;i<=4;i++){
                     X*=a[i][r[i].x][r[i].y];
               }
               KQ = KQ + X;
              // printf("%d %lld\n",l,KQ);
          }
          printf("%lld\n",KQ);
      }

      //getch();
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
typedef long long ll;
using namespace std;

int dx[4] = {2,2,1,1};
int dy[4] = {2,1,2,1};
int b[6],n;
ll a[4][4];

bool ok()
{
     int x0 = -dx[b[0]],y0 = -dy[b[0]];
     int x1 = -dx[b[1]],y1 = dy[b[1]];
     int x2 = dx[b[2]],y2 = -dy[b[2]];
     int x3 = dx[b[3]],y3 = dy[b[3]];
     int area = (x0 * y1 - x1 * y0) + (x1 * y3 - x3 * y1) + (x3 * y2 - x2 * y3) + (x2 * y0 - x0 * y2);
     return ((abs(area) & 1) == 0);
};

int main()
{
//    freopen("nicequad.in","r",stdin);
//    freopen("nicequad.ou","w",stdout);
    int T;
    scanf("%d", &T);
    while (T--)
    {
          scanf("%d", &n);
          memset(a,0,sizeof(a));
          for (int i = 0; i < n; i++)
          {
              int x,y;
              scanf("%d %d", &x, &y);
              if (!x || !y) continue;
              int num = (x > 0) * 2 + (y > 0);
              x = abs(x);  y = abs(y);
              int pos = (x & 1) * 2 + (y & 1);
//              cout << num << ' ' << pos << endl;
              a[num][pos]++;
          };
          ll ret = 0;
          for (int i = 0; i < 256; i++)
          {
              int p = i;
              for (int j = 0; j < 4; j++)
              {
                  b[j] = p % 4;  p /= 4;
              };
              b[4] = b[0];
              if (ok())
              {
//                 for (int j = 0; j < 4; j++) cout << b[j] << ' ';
//                 cout << endl;
                 ll add  =1;  
                 for (int j = 0; j < 4; j++) add *= (ll) a[j][b[j]];
                 ret += add;
              };
          };
          cout << ret << endl;
    };    
};

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define Rep(i,n) for(int i=0;i<(n);++i)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define fi first
#define se second
#define pb push_back
#define MP make_pair

int c[4][2][2];

int main() {
    int st;
    scanf("%d",&st);
    Rep(t,st){
        int n,x,y;
        scanf("%d",&n);
        memset(c,0,sizeof(c));
        Rep(i,n){
            scanf("%d%d",&x,&y);
            int d=x>0?(y>0?0:1):(y<0?2:3);
            if(x!=0&&y!=0)++c[d][x%2!=0][y%2!=0];
        }
        long long total=0;
        Rep(b,1<<8){
            int u[4],v[4],s=0;
            Rep(i,4)u[i]=(b&(1<<(2*i)))!=0,v[i]=(b&(1<<(2*i+1)))!=0;
            Rep(i,4) s+=(u[i]-u[(i+1)%4])*(v[i]+v[(i+1)%4]);
            if(s%2==0){
                long long r=1;
                Rep(i,4)r*=c[i][u[i]][v[i]];
                total+=r;
            }
        }
        cout<<total<<endl;
    }

    return 0;   
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.