#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef long double ld;
struct pii{
int x, y;
pii(int x, int y): x(x), y(y){}
pii operator -(pii a){return pii(x-a.x, y-a.y);}
bool operator <(pii a){return (x<a.x || (x==a.x && y<a.y));}
ld dl(){return sqrt(x*1ll*x+y*1ll*y);}
};
ll cross(pii a, pii b){
return a.x*1ll*b.y-a.y*1ll*b.x;
}
ll cross(pii a, pii b, pii c){
return cross(b-a, c-a);
}
int sgn(ll a){
if(a==0)return 0;
return a/abs(a);
}
ll dot(pii a, pii b){
return a.x*1ll*b.x+b.y*1ll*a.y;
}
ll dot(pii a, pii b, pii c){
return dot(b-a, c-a);
}
typedef pair<pii, pii> odc;
vector<pii> V;
bool check(odc tt){
vector<ld> A, B;
for(int i=0; i<V.size(); i++){
ll t=sgn(cross(tt.st, V[i], tt.nd));
if(t>0){
A.push_back(dot(tt.st, tt.nd, V[i])/(V[i]-tt.st).dl());
B.push_back(dot(tt.nd, tt.st, V[i])/(V[i]-tt.nd).dl());
}
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
//cout<<tt.st.x<<" "<<tt.st.y<<" "<<tt.nd.x<<" "<<tt.nd.y<<"\n";
//cout<<A.size()<<"\n";
for(int i=0; i<V.size(); i++){
ll t=sgn(cross(tt.st, V[i], tt.nd));
if(t<0){
ld k=dot(tt.st, tt.nd, V[i])/(V[i]-tt.st).dl(), l=dot(tt.nd, tt.st, V[i])/(V[i]-tt.nd).dl();
k=-k;
l=-l;
if(lower_bound(A.begin(), A.end(), k)-A.begin()+lower_bound(B.begin(), B.end(), l)-B.begin()!=A.size()){
return 0;
}
}
}
return 1;
}
int main(){
int n;
cin>>n;
V.resize(n, pii(0, 0));
for(pii &i:V){
cin>>i.x>>i.y;
}
int ans=0;
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
ans+=check(odc(V[i], V[j]));
}
}
cout<<ans;
}
Compilation message
geometrija.cpp: In function 'bool check(odc)':
geometrija.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pii>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
geometrija.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pii>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
geometrija.cpp:52:96: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__normal_iterator<long double*, std::vector<long double> >::difference_type' {aka 'long int'} and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | if(lower_bound(A.begin(), A.end(), k)-A.begin()+lower_bound(B.begin(), B.end(), l)-B.begin()!=A.size()){
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
204 KB |
Output is correct |
2 |
Correct |
3 ms |
292 KB |
Output is correct |
3 |
Correct |
3 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
2 ms |
204 KB |
Output is correct |
6 |
Correct |
2 ms |
288 KB |
Output is correct |
7 |
Correct |
3 ms |
204 KB |
Output is correct |
8 |
Correct |
3 ms |
204 KB |
Output is correct |
9 |
Correct |
3 ms |
204 KB |
Output is correct |
10 |
Correct |
3 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
204 KB |
Output is correct |
2 |
Correct |
3 ms |
292 KB |
Output is correct |
3 |
Correct |
3 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
2 ms |
204 KB |
Output is correct |
6 |
Correct |
2 ms |
288 KB |
Output is correct |
7 |
Correct |
3 ms |
204 KB |
Output is correct |
8 |
Correct |
3 ms |
204 KB |
Output is correct |
9 |
Correct |
3 ms |
204 KB |
Output is correct |
10 |
Correct |
3 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
378 ms |
288 KB |
Output is correct |
13 |
Correct |
382 ms |
296 KB |
Output is correct |
14 |
Correct |
286 ms |
332 KB |
Output is correct |
15 |
Correct |
256 ms |
292 KB |
Output is correct |
16 |
Correct |
370 ms |
296 KB |
Output is correct |
17 |
Correct |
371 ms |
324 KB |
Output is correct |
18 |
Correct |
366 ms |
288 KB |
Output is correct |
19 |
Correct |
363 ms |
204 KB |
Output is correct |
20 |
Correct |
376 ms |
284 KB |
Output is correct |
21 |
Correct |
415 ms |
204 KB |
Output is correct |
22 |
Correct |
370 ms |
204 KB |
Output is correct |
23 |
Correct |
365 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
204 KB |
Output is correct |
2 |
Correct |
3 ms |
292 KB |
Output is correct |
3 |
Correct |
3 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
2 ms |
204 KB |
Output is correct |
6 |
Correct |
2 ms |
288 KB |
Output is correct |
7 |
Correct |
3 ms |
204 KB |
Output is correct |
8 |
Correct |
3 ms |
204 KB |
Output is correct |
9 |
Correct |
3 ms |
204 KB |
Output is correct |
10 |
Correct |
3 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
378 ms |
288 KB |
Output is correct |
13 |
Correct |
382 ms |
296 KB |
Output is correct |
14 |
Correct |
286 ms |
332 KB |
Output is correct |
15 |
Correct |
256 ms |
292 KB |
Output is correct |
16 |
Correct |
370 ms |
296 KB |
Output is correct |
17 |
Correct |
371 ms |
324 KB |
Output is correct |
18 |
Correct |
366 ms |
288 KB |
Output is correct |
19 |
Correct |
363 ms |
204 KB |
Output is correct |
20 |
Correct |
376 ms |
284 KB |
Output is correct |
21 |
Correct |
415 ms |
204 KB |
Output is correct |
22 |
Correct |
370 ms |
204 KB |
Output is correct |
23 |
Correct |
365 ms |
204 KB |
Output is correct |
24 |
Execution timed out |
1084 ms |
332 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |