POJ 2737 Swamp Things(スロープ判定マルチポイント共線)
2955 ワード
Swamp Things
标题:最も多くの共線を判断する点数
考え方:すべての点対の傾きを保存して並べ替えて、どれだけ同じ説明があるかを見て、共線注意で傾きが存在しない場合を判断します.
参考コード:
map TLE了慎重用STL
标题:最も多くの共線を判断する点数
考え方:すべての点対の傾きを保存して並べ替えて、どれだけ同じ説明があるかを見て、共線注意で傾きが存在しない場合を判断します.
参考コード:
map TLE了慎重用STL
//
// Created by TaoSama on 2015-06-12
// Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
const double EPS = 1e-10;
int n, x[1005], y[1005];
double k[1005];
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
// freopen("out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int kase = 0;
while(scanf("%d", &n) == 1 && n) {
for(int i = 1; i <= n; ++i) scanf("%d%d", x + i, y + i);
int ans = 0;
for(int i = 1; i <= n; ++i) {
int cnt = 0;
for(int j = i + 1; j <= n; ++j) {
if(x[i] == x[j]) k[cnt++] = INF;
else k[cnt++] = (y[i] - y[j]) * 1.0 / (x[i] - x[j]);
}
sort(k, k + cnt);
for(int j = 0; j < cnt; ++j) {
int ct = 1;
while(j + 1 < cnt && abs(k[j] - k[j + 1]) < EPS)
++j, ++ct;
ans = max(ct, ans);
}
}
ans += 1;
if(ans < 4) ans = 0;
printf("Photo %d: %d points eliminated
", ++kase, ans);
}
return 0;
}
/*
int n, x[1005], y[1005];
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
// freopen("out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int kase = 0;
while(scanf("%d", &n) == 1 && n) {
for(int i = 1; i <= n; ++i) scanf("%d%d", x + i, y + i);
int ans = 0;
for(int i = 1; i <= n; ++i) {
int Max = 0;
map<double, int> slope;
for(int j = i + 1; j <= n; ++j) {
double t;
if(x[i] == x[j]) t = INF;
else t = (y[i] - y[j]) * 1.0 / (x[i] - x[j]);
//cout << t << endl;
if(!slope.count(t)) {
slope[t] = 2;
Max = max(Max, 2);
} else {
slope[t]++;
Max = max(Max, slope[t]);
}
}
ans = max(ans, Max);
}
if(ans < 4) ans = 0;
printf("Photo %d: %d points eliminated
", ++kase, ans);
}
return 0;
}
*/