Submission #483867

#TimeUsernameProblemLanguageResultExecution timeMemory
483867sam571128Geometrija (COCI21_geometrija)C++17
50 / 110
1062 ms664 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 = 0; vector<pair<point,point>> tr; for(int a = 0; a < n; a++){ for(int b = a+1; b < n; b++){ for(auto [c,d] : tr){ if(intersect(arr[a],arr[b],c,d)){ goto nxt; } } tr.push_back({arr[a],arr[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])){ goto nxt; } } } ans++; nxt:; } } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...