結果

問題 No.1041 直線大学
ユーザー wk
提出日時 2020-05-01 21:44:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 5,798 bytes
コンパイル時間 1,996 ms
コンパイル使用メモリ 169,928 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-16 07:52:12
合計ジャッジ時間 2,655 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define INF 5000000000000000
using namespace std;
struct Edge{
int to;
long weight;
Edge(int t, long w) : to(t), weight(w) {}
};
long modpow(long a, long n, long mod) {
long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
// a^{-1} mod
long modinv(long a, long mod) {
return modpow(a, mod - 2, mod);
}
struct compare1 {
bool operator()(const pair<long, long>& value,
const long& key)
{
return (value.first < key);
}
bool operator()(const long& key,
const pair<long, long>& value)
{
return (key < value.first);
}
};
struct RMQ {
vector<int> a;
int inf = 2000000000; // 2*10^9
int n = 1;
RMQ(int n_ = 1){
init(n_);
}
void init(int n_ = 1){
while(n < n_) n *= 2;
a.resize(2*n-1);
REP(i, 2*n-1) a[i] = inf;
}
//k(0-indexed)b
void update(int k, int b){
k += n-1;
a[k] = b;
while(k > 0){
k = (k-1)/2;
a[k] = min(a[2*k+1], a[2*k+2]);
}
}
//[a,b)
int query_first(int c, int b){
return query(c, b, 0, 0, n);
}
//k : , l, r[l, r)
int query(int c, int b, int k, int l, int r){
if(r <= c || b <= l) return inf;
if(c <= l && r <= b) return a[k];
else{
int vl = query(c, b, k*2+1, l, (l+r)/2);
int vr = query(c, b, k*2+2, (l+r)/2, r);
return min(vl, vr);
}
}
};
struct UnionFind {
vector<int> par;
vector<int> rank;
UnionFind(int n = 1){
init(n);
}
void init(int n = 1){
par.resize(n);
rank.resize(n);
REP(i, n) par[i] = i, rank[i] = 0;
}
int root(int x){
if(par[x] == x) return x;
else return par[x] = root(par[x]);
}
bool issame(int x, int y){
return root(x) == root(y);
}
bool merge(int x, int y){
x = root(x); y = root(y);
if(x == y) return false;
if(rank[x] < rank[y]) swap(x, y);
if(rank[x] == rank[y]) rank[x]++;
par[y] = x;
return true;
}
};
template<class Abel> struct weightedUnionFind{
vector<int> par;
vector<int> rank;
vector<Abel> diff_weight;
weightedUnionFind(int n = 1, Abel SUM_UNITY = 0){
init(n, SUM_UNITY);
}
void init(int n = 1, Abel SUM_UNITY = 0){
par.resize(n); rank.resize(n); diff_weight.resize(n);
REP(i, n) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
}
int root(int x){
if(par[x] == x) return x;
else{
int r = root(par[x]);
diff_weight[x] += diff_weight[par[x]];
return par[x] = r;
}
}
Abel weight(int x){
root(x);
return diff_weight[x];
}
bool issame(int x, int y){
return root(x) == root(y);
}
bool merge(int x, int y, Abel w){
w += weight(x); w -= weight(y);
x = root(x); y = root(y);
if(x == y) return false;
if(rank[x] < rank[y]) swap(x, y), w = -w;
if(rank[x] == rank[y]) rank[x]++;
par[y] = x;
diff_weight[y] = w;
return true;
}
Abel diff(int x, int y){
return weight(y) - weight(x);
}
};
using Graph = vector<vector<int>>;
using P = pair<long, long>;
/*
void dijkstra(int s, int V, Graph &G, long* d){
priority_queue<P, vector<P>, greater<P>> pque;
fill(d, d + V, INF);
d[s] = 0;
pque.push(P(0, s));
while(!pque.empty()){
P p = pque.top(); pque.pop();
int now = p.second;
if(d[now] < p.first) continue;
REP(i, G[now].size()){
Edge e = G[now][i];
if(d[e.to] > d[now] + e.weight){
d[e.to] = d[now] + e.weight;
pque.push(P(d[e.to], e.to));
}
}
}
}
*/
int GCD(int a, int b){
if(b == 0) return a;
if(a < b) return GCD(b, a);
else return GCD(b, a%b);
}
struct BIT{
vector<long> dat;
int n = 1;
BIT(int nn = 1){
init(nn);
}
void init(int nn = 1){
while(n < nn) n *= 2;
dat.resize(n+1);
REP(i, n+1) dat[i] = 0l;
}
//1-indexed!!!!
void add(int i, long x){
while(i <= n){
dat[i] += x;
i += (i&(-i));
}
}
//1-indexed!!!!!
long get_sum(int i){
long ans = 0l;
while(i > 0){
ans += dat[i];
i -= (i & (-i));
}
return ans;
}
};
int main()
{
int N; cin >> N;
int X[105], Y[105];
REP(i, N) cin >> X[i] >> Y[i];
int ans = 0;
REP(i, N) for(int j=i+1; j<N;j++){
if(X[i]!=X[j] && Y[i]!=Y[j]){
int temp = 0;
int gcd = GCD(abs(X[i] - X[j]), abs(Y[i] - Y[j]));
int x = (X[i] - X[j]) / gcd;
int y = (Y[i] - Y[j]) / gcd;
REP(k, N) if((X[i] -X[k])%x==0 && (Y[i] - Y[k])%y==0){
if((X[i] - X[k])/x == (Y[i]-Y[k])/y) temp++;
}
//cout << temp << endl;
ans = max(ans, temp);
}else{
if(X[i]==X[j]){
int temp = 0;
REP(k, N) if(X[i] == X[k]) temp++;
ans = max(ans, temp);
}else{
int temp = 0;
REP(k, N) if(Y[i] == Y[k]) temp++;
ans = max(ans, temp);
}
}
}
cout << ans << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0