제출 #483711

#제출 시각아이디문제언어결과실행 시간메모리
483711sam571128Geometrija (COCI21_geometrija)C++17
20 / 110
1088 ms1584 KiB
#include <bits/stdc++.h> #define int long long #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; typedef pair<int,int> point; #define x first #define y second int operator^(point a, point b){ return a.x*b.y-a.y*b.x; } int operator*(point a, point b){ return a.x*b.x+a.y*b.y; } point operator-(point a, point b){ return {a.x-b.x,a.y-b.y}; } point operator+(point a, point b){ return {a.x+b.x,a.y+b.y}; } int ori(point a, point b, point c){ int tmp = (b-a)^(c-a); if(tmp == 0) return 0; return abs(tmp)/tmp; } int intersect(point a, point b, point c, point d){ int abc = ori(a,b,c); int abd = ori(a,b,d); int cda = ori(c,d,a); int cdb = ori(c,d,b); if(abc*abd < 0 && cda*cdb < 0) return true; else return false; } signed main(){ fastio int n; cin >> n; vector<point> arr; for(int i = 0;i < n;i++){ int a,b; cin >> a >> b; arr.push_back({a,b}); } int ans = n*(n-1)/2; map<point,int> m; for(int a = 0; a < n; a++){ for(int b = a+1; b < n; b++){ for(int c = 0; c < n; c++){ for(int d = c+1; d < n; d++){ if(intersect(arr[a],arr[b],arr[c],arr[d])){ m[{a,b}]++; m[{c,d}]++; } } } } } cout << ans-m.size() << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...