比赛 20161114 评测结果 RRRRRRRRRR
题目名称 欺负萌新的Rapiz 最终得分 0
用户昵称 最长上升子序列 运行时间 0.002 s
代码语言 C++ 内存使用 12.07 MiB
提交时间 2016-11-14 10:48:33
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define long long lnt;
using namespace std;

const int up=40+1,maxN=1000+5;
bool vis[maxN][maxN];
int node[up][up][up][up],n;
struct nodes
{
    int x,y,z,w;
    bool operator < (const nodes& b) const
    {
        if(x!=b.x) return x<b.x;
        else if(y!=b.y) return y<b.y;
        else if(z!=b.z) return z<b.z;
        else if(w!=b.w) return w<b.w;
    }
} no[maxN];

int main()
{
    freopen("xumingshi.in","r",stdin);
    freopen("xumingshi.out","w",stdout);
    int dx,dy,dz,dw,mx,y,z,w,sum,ans=2;

    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d %d %d",&no[i].x,&no[i].y,&no[i].z,&no[i].w);
        no[i].x+=20;no[i].y+=20;no[i].z+=20;no[i].w+=20;
    }
    sort(no,no+n);
    for(int i=0;i<n;i++) node[no[i].x][no[i].y][no[i].z][no[i].w]=i;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++) if(!vis[i][j])
        {
            if(no[i].x==no[j].x) sum=2;
            else sum=1;
            dx=no[i].x-no[j].x;dy=no[i].y-no[j].y;
            dz=no[i].z-no[j].z;dw=no[i].w-no[j].w;
            if(dx==0)
            {
                if(dy) dx=dy;
                else if(dz) dx=dz;
                else dx=dw;
            }
            for(int k=no[j].x;k<=no[n-1].x;k++)
            {
                mx=k-no[j].x;
                if(mx*dy%dx!=0 || mx*dz%dx!=0 || mx*dw%dx!=0) continue;
                y=no[j].y+mx*dy/dx;
                z=no[j].z+mx*dz/dx;
                w=no[j].w+mx*dw/dx;
                //cout<<k<<' '<<y<<' '<<z<<' '<<w<<endl;
                if(y>40 || z>40 || w>40) continue;
                if(node[k][y][z][w])
                {
                    vis[j][node[k][y][z][w]]=1,sum++;
                    //cout<<k<<' '<<y<<' '<<z<<' '<<w<<endl;
                }
            }
            ans=max(ans,sum);
        }
    }
    printf("%d\n",ans);

    return 0;
}