记录编号 204420 评测结果 AAAAAWAAWA
题目名称 [SYOI 2015] Asm.Def找燃料 最终得分 80
用户昵称 Gravatar坐看321JG虐场 是否通过 未通过
代码语言 C++ 运行时间 0.035 s
提交时间 2015-11-04 12:15:35 内存使用 0.22 MiB
显示代码纯文本
//
//  main.cpp
//  asm_fuel
//
//  Created by Qing Liu on 15/11/4.
//  Copyright © 2015年 Qing Liu. All rights reserved.
//

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define maxn 110
using namespace std;
typedef pair<int, int > pi;
pi dian[maxn];
set<int>asd;
int gcd(int x,int y){
    if (y!=0) {
        return gcd(y,x%y);
    }
    return x;
}
int main() {
    freopen("asm_fuel.in", "r", stdin);
    freopen("asm_fuel.out", "w", stdout);
    int n;
    cin>>n;
    for (int i=0; i<n; i++) {
        int x,y;
        cin>>x>>y;
        pi asd(x,y);
        dian[i]=asd;
    }
    int maxx=0;
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            if (dian[i].first==dian[j].first&&dian[i].second==dian[j].second) {
                continue;
            }
            int ans=0;
            int x=dian[j].first-dian[i].first;
            int y=dian[j].second-dian[i].second;
            x=abs(x);
            y=abs(y);
            int ggcd=gcd(x, y);
            x/=ggcd;
            y/=ggcd;
            int hash=x*11000+y;
            if (asd.count(hash)) {
                continue;
            }
            asd.insert(hash);
            for (int k=0; k<n; k++) {
                if (ans+n-k<=maxx) {
                    break;
                }
                int tx=dian[k].first-dian[i].first;
                int ty=dian[k].second-dian[i].second;
                if (x*ty-y*tx==0) {
                    ans++;
                }
            }
            if (ans>maxx) {
                maxx=ans;
            }
        }
    }
    cout<<maxx;
    return 0;
}