1616C - Representative Edges - CodeForces Solution

// omga

#include <bits/stdc++.h>

#define vlong vector<long>
#define vint vector<int>
#define vchar vector<char>
#define vbool vector<bool>
#define vull vector<unsigned long long>

#define CININT(n) INTCIN(n);
#define INTCIN(n) int n; cin >> n;
#define INTCINVINTCIN(a, n) INTCIN(n); CINVINT(a, n);
#define CIN(n) cin >> n;
#define COUT(n) cout << n;
#define CINV(a, n) for (int i = 0; i < n; i++) {cin >> a[i];}
#define CINVINT(a, n) vint a(n); CINV(a, n);
#define COUTV(a, n) for (int i = 0; i < n; i++) {cout << a[i] << " ";}
#define ENDL cout << "\n";
#define SORT(a) sort(a.begin(), a.end())
#define TWONUMV(n, k, a) INTCIN(n); INTCIN(k); CINVINT(a, n);
#define NO cout << "NO"; return;
#define YES cout << "YES"; return;
#define IMPOSSIBLE cout << "IMPOSSIBLE"; return;
#define DEBUG(s) cout << "<d:" << s << ">";
using namespace std;

void cap_time(int& h, int& m) { // for time-related problems
	while (m >= 60) {
		h++;
		m -= 60;
	}
	h %= 24;
}

//CININT(n);
//ICVK(n, k, a);
//INTCINVINTCIN(a, n);
	
ifstream fin("C.in");
ofstream fout("C.out");
/*//comment out to fin-fout
#define cin fin
#define cout fout
//*/

// You can do it!
void solve() {
	INTCINVINTCIN(a, n);
	int maxe = -0;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			int al = a[i], ar = a[j];
			long double d = (ar - al) / (long double)(j - i);
			//DEBUG(d);
			int e = 0;
			for (int h = i; h < j; h++) {
				if (abs((long double)(d * (h - i) + al) - (long double)a[h]) < 0.000001) {
					e++;
				}
			}
			maxe = max(e, maxe);
		}
	}
	cout << n - maxe - 1;

}

int main() {
	// comment out star below to switch
	/*
	solve();
	/*/
	int t;
	cin >> t;
	while (t--) {
		solve();
		ENDL;
	}
	//*/
}