#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define int long long
#define sz(a) (int)a.size()
const int mod = 1e9 + 7;
const int N = 2e5+ 100;
int crossproduct(pair <int, int> a, pair <int, int> b)
{
return a.X * b.Y - a.Y * b.X;
}
bool cmp(pair <pair <int, int>, int> a, pair <pair <int, int>, int> b)
{
if(a.X.X * b.X.X < 0)
{
return a.X.X > b.X.X;
}
if(a.X.X == 0)
{
return b.X.X < 0 || a.X.Y > 0;
}
if(b.X.X == 0)
{
return a.X.X > 0 && b.X.Y < 0;
}
return crossproduct(a.X, b.X) < 0;
}
signed main()
{
// ifstream cin("input1.txt.4c");
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector <pair <int, int> > x(n);
int cnt[n][n];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cnt[i][j] = 0;
}
}
for(int i = 0; i < n; i++)
{
cin >> x[i].X >> x[i].Y;
}
vector <int> coun(n);
for(int i = 0; i < n; i++)
{
vector <pair <pair <int, int>, int> > t;
for(int j = 0; j < n; j++)
{
if(i != j)
{
t.push_back({{x[j].X - x[i].X, x[j].Y - x[i].Y}, j});
}
}
sort(t.begin(), t.end(), cmp);
int it = 0;
//cout << i << "\n";
for(int j = 0; j < n - 1; j++)
{
// cout << t[j].X.X << " " << t[j].X.Y << " " << t[j].Y << "\n";
while(it != n - 1 + j && (j == it || crossproduct(t[j].X, t[it % (n - 1)].X) < 0))
{
it++;
}
// cout << "A " << it << " ";
coun[j] = (n - 1 + j) - it;
//cout << coun[j] << "\n";
}
int sum = 0;
it = 1;
for(int j = 1; j < n - 1; j++)
{
sum += coun[j];
}
for(int j = 0; j < n - 1; j++)
{
while(it != n - 1 + j && (it <= j || crossproduct(t[j].X, t[it % (n - 1)].X) < 0))
{
sum -= coun[it % (n - 1)];
it++;
}
int k = it - j - 1;
// cout << i << " " << t[j].Y << " " << sum + k * (k - 1) / 2 << "\n";
cnt[i][t[j].Y] += sum + k * (k - 1) / 2;
sum += coun[j];
}
}
int ans = 0;
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
int d = cnt[i][j] + cnt[j][i];
int k1 = 0, k2 = 0;
int A = x[j].Y - x[i].Y;
int B = x[i].X - x[j].X;
int C = -x[i].X * A - x[i].Y * B;
for(int t = 0; t < n; t++)
{
if(A * x[t].X + B * x[t].Y + C < 0)
{
k1++;
}
else if(A * x[t].X + B * x[t].Y + C > 0)
{
k2++;
}
}
d -= k1 * (k1 - 1) / 2;
d -= k2 * (k2 - 1) / 2;
// cout << d << " ";
if(d == (n - 2) * (n - 3) / 2)
{
ans++;
}
}
//cout << "\n";
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
316 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
316 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
22 ms |
588 KB |
Output is correct |
13 |
Correct |
22 ms |
592 KB |
Output is correct |
14 |
Correct |
17 ms |
576 KB |
Output is correct |
15 |
Correct |
15 ms |
564 KB |
Output is correct |
16 |
Correct |
20 ms |
656 KB |
Output is correct |
17 |
Correct |
21 ms |
588 KB |
Output is correct |
18 |
Correct |
21 ms |
648 KB |
Output is correct |
19 |
Correct |
22 ms |
644 KB |
Output is correct |
20 |
Correct |
20 ms |
636 KB |
Output is correct |
21 |
Correct |
20 ms |
640 KB |
Output is correct |
22 |
Correct |
22 ms |
588 KB |
Output is correct |
23 |
Correct |
21 ms |
648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
316 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
22 ms |
588 KB |
Output is correct |
13 |
Correct |
22 ms |
592 KB |
Output is correct |
14 |
Correct |
17 ms |
576 KB |
Output is correct |
15 |
Correct |
15 ms |
564 KB |
Output is correct |
16 |
Correct |
20 ms |
656 KB |
Output is correct |
17 |
Correct |
21 ms |
588 KB |
Output is correct |
18 |
Correct |
21 ms |
648 KB |
Output is correct |
19 |
Correct |
22 ms |
644 KB |
Output is correct |
20 |
Correct |
20 ms |
636 KB |
Output is correct |
21 |
Correct |
20 ms |
640 KB |
Output is correct |
22 |
Correct |
22 ms |
588 KB |
Output is correct |
23 |
Correct |
21 ms |
648 KB |
Output is correct |
24 |
Execution timed out |
1083 ms |
8176 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |