Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define fst first
- #define snd second
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> ii;
- const double inf = 1e100, eps = 1e-9;
- const double PI = acos(-1.0L);
- int cmp (double a, double b = 0) {
- if (abs(a-b) < eps) return 0;
- return (a < b) ? -1 : +1;
- }
- struct PT {
- double x, y;
- PT(double x = 0, double y = 0) : x(x), y(y) {}
- PT operator + (const PT &p) const { return PT(x+p.x, y+p.y); }
- PT operator - (const PT &p) const { return PT(x-p.x, y-p.y); }
- PT operator * (double c) const { return PT(x*c, y*c); }
- PT operator / (double c) const { return PT(x/c, y/c); }
- bool operator <(const PT &p) const {
- if(cmp(x, p.x) != 0) return x < p.x;
- return cmp(y, p.y) < 0;
- }
- bool operator ==(const PT &p) const {
- return (cmp(x, p.x) || cmp(y, p.y));
- }
- };
- double dot (PT p, PT q) { return p.x * q.x + p.y*q.y; }
- double cross (PT p, PT q) { return p.x * q.y - p.y*q.x; }
- bool parallel (PT a, PT b, PT c, PT d) {
- return cmp(cross(b - a, c - d)) == 0;
- }
- PT computeLineIntersection (PT a, PT b, PT c, PT d) {
- b = b - a; d = c - d; c = c - a;
- assert(cmp(cross(b, d)) != 0); // checar sse sao paralelos
- return a + b * cross(c, d) / cross(b, d);
- }
- int n;
- int main(){
- ios::sync_with_stdio(0); cin.tie(0);
- while(cin >> n && n){
- vector<pair<PT, PT>> line;
- for(int i = 0; i < n; ++i){
- int x1, y1, x2, y2;
- cin >> x1 >> y1 >> x2 >> y2;
- line.push_back({PT(x1, y1), PT(x2, y2)});
- }
- vector<vector<int>> adj(n * n, vector<int>());
- map<PT, int> mp;
- int c = 0;
- for(int i = 0; i < n; ++i){
- vector<PT> now;
- for(int j = 0; j < n; ++j){
- if(i == j) continue;
- if(!parallel(line[i].fst, line[i].snd, line[j].fst, line[j].snd)){
- PT aux = computeLineIntersection(line[i].fst, line[i].snd, line[j].fst, line[j].snd);
- now.push_back(aux);
- }
- }
- sort(now.begin(), now.end());
- for(int j = 1; j < ((int)now.size()); ++j){
- if(!mp.count(now[j-1])){
- mp[now[j-1]] = c++;
- }
- if(!mp.count(now[j])){
- mp[now[j]] = c++;
- }
- adj[mp[now[j]]].push_back(mp[now[j-1]]);
- adj[mp[now[j-1]]].push_back(mp[now[j]]);
- }
- }
- bool achou[c];
- int ans = 0;
- for(int i = 0; i < c; ++i){
- memset(achou, 0, sizeof achou);
- for(int j = 0; j < adj[i].size(); ++j){
- achou[adj[i][j]] = 1;
- for(auto k : adj[adj[i][j]]){
- if(achou[k]) ans++;
- }
- }
- }
- cout << ans/3 << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement