POJ 2737 Swamp Things(スロープ判定マルチポイント共線)


Swamp Things
标题:最も多くの共線を判断する点数
考え方:すべての点対の傾きを保存して並べ替えて、どれだけ同じ説明があるかを見て、共線注意で傾きが存在しない場合を判断します.
参考コード:
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; } */