#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define F first
#define S second
#define sz(x) (int)x.size()
#define el "\n"
#define pi (ld)acos(-1.0)
//#pragma GCC target("avx2")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 1e3 + 500;
int n;
int x[N], y[N];
int sg(ll x) {
if (x < 0) {
return 0;
}
return 1;
}
ll det(ll a, ll b, ll c, ll d) {
return (a * d - b * c);
}
ld to_degrees(ld x) {
return x * ld(180) / pi;
}
ld get_alpha(ld a, ld b, ld c) {
// cerr << acos((a + b - c) / (2.0 * sqrt((ld)a) * sqrt((ld)b))) << el;
return to_degrees(acos((a + b - c) / (2.0 * sqrt((ld)a) * sqrt((ld)b))));
}
ll dist(ll a, ll b, ll c, ll d) {
return ((a - c) * (a - c) + (b - d) * (b - d));
}
vector <pair <ld, ld> > vc[2];
ld sf[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
// cerr.precision(10);
// cerr << fixed;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
}
int ans = 0;
for (int a = 0; a < n; a++) {
for (int b = a + 1; b < n; b++) {
vector <int> emp;
for (int i = 0; i < n; i++) {
if (i != a && i != b) {
emp.pb(i);
}
}
bool bad = 0;
for (int i = 0; i < n - 2 && !bad; i++) {
int c = emp[i];
for (int j = i + 1; j < n - 2 && !bad; j++) {
int d = emp[j];
int s1 = sg(det(x[b] - x[c], y[b] - y[c], x[d] - x[c], y[d] - y[c]));
int s2 = sg(det(x[d] - x[b], y[d] - y[b], x[a] - x[b], y[a] - y[b]));
int s3 = sg(det(x[a] - x[d], y[a] - y[d], x[c] - x[d], y[c] - y[d]));
if (s1 == s2 && s1 == s3 && s1 == 0) {
bad = 1;
break;
}
}
}
if (!bad) {
ans++;
}
}
}
// for (int a = 0; a < n; a++) {
// for (int b = a + 1; b < n; b++) {
// vc[0].clear(); vc[1].clear();
// for (int c = 0; c < n; c++) {
// if (a == c || b == c) {
// continue;
// }
// int sgn = sg(det(x[b] - x[a], y[b] - y[a], x[c] - x[a], y[c] - y[a]));
// ll ab = dist(x[a], y[a], x[b], y[b]);
// ll ac = dist(x[a], y[a], x[c], y[c]);
// ll bc = dist(x[b], y[b], x[c], y[c]);
// vc[sgn].pb({get_alpha(ab, bc, ac), get_alpha(ac, ab, bc)});
// }
//
// sort(all(vc[0]),
// [&](pair <ld, ld> a, pair <ld, ld> b) {
// return a.F > b.F;
// });
// sort(all(vc[1]),
// [&](pair <ld, ld> a, pair <ld, ld> b) {
// return a.F < b.F;
// });
//
// sf[sz(vc[0])] = 1e9;
// for (int j = sz(vc[0]) - 1; j >= 0; j--) {
// sf[j] = min(sf[j + 1], vc[0][j].S);
// }
// int i = 0;
// bool bad = 0;
// for (auto p : vc[1]) {
// ld alpha = p.F;
// ld beta = p.S;
// while (i < sz(vc[0]) && alpha + vc[0][i].F > 180) {
// i++;
// }
// if (sf[i] + beta < 180.0) {
// bad = 1;
// break;
// }
// }
// if (!bad) {
// ans++;
// }
// }
// }
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
