#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<double, double> pi;
 
struct line{
    double a, b, c;
};
 
pi cross(line p, line q){
    double base = p.a * q.b - p.b * q.a;
    if(fabs(base) < 1e-5) return pi(1e9, 1e9);
    return pi((p.b * q.c - q.b * p.c) / base, (p.c * q.a - q.c * p.a) / base);
}

double func(line a, pi b){
    return a.a * b.first + a.b * b.second + a.c;
}
 
void half_plane_intersect(vector<line> &v, vector<pi> &ret){
	int n = v.size();
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            pi crs = cross(v[i], v[j]);
            if(fabs(crs.first - 1e9) < 1e-4) continue;
            bool bad = 0;
            for(int k=0; k<n; k++){
                if(func(v[k], crs) < -1e-4){
                    bad = 1;
                    break;
                }
            }
            if(!bad) ret.push_back(crs);
        }
    }
 
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8bWF0aC5oPgojaW5jbHVkZSA8bGltaXRzLmg+CiNpbmNsdWRlIDxzdGFjaz4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8ZnVuY3Rpb25hbD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDxkZXF1ZT4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDxiaXRzZXQ+CiNpbmNsdWRlIDxpb3N0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgbGludDsKdHlwZWRlZiBsb25nIGRvdWJsZSBsbGY7CnR5cGVkZWYgcGFpcjxkb3VibGUsIGRvdWJsZT4gcGk7CiAKc3RydWN0IGxpbmV7CiAgICBkb3VibGUgYSwgYiwgYzsKfTsKIApwaSBjcm9zcyhsaW5lIHAsIGxpbmUgcSl7CiAgICBkb3VibGUgYmFzZSA9IHAuYSAqIHEuYiAtIHAuYiAqIHEuYTsKICAgIGlmKGZhYnMoYmFzZSkgPCAxZS01KSByZXR1cm4gcGkoMWU5LCAxZTkpOwogICAgcmV0dXJuIHBpKChwLmIgKiBxLmMgLSBxLmIgKiBwLmMpIC8gYmFzZSwgKHAuYyAqIHEuYSAtIHEuYyAqIHAuYSkgLyBiYXNlKTsKfQoKZG91YmxlIGZ1bmMobGluZSBhLCBwaSBiKXsKICAgIHJldHVybiBhLmEgKiBiLmZpcnN0ICsgYS5iICogYi5zZWNvbmQgKyBhLmM7Cn0KIAp2b2lkIGhhbGZfcGxhbmVfaW50ZXJzZWN0KHZlY3RvcjxsaW5lPiAmdiwgdmVjdG9yPHBpPiAmcmV0KXsKCWludCBuID0gdi5zaXplKCk7CiAgICBmb3IoaW50IGk9MDsgaTxuOyBpKyspewogICAgICAgIGZvcihpbnQgaj1pKzE7IGo8bjsgaisrKXsKICAgICAgICAgICAgcGkgY3JzID0gY3Jvc3ModltpXSwgdltqXSk7CiAgICAgICAgICAgIGlmKGZhYnMoY3JzLmZpcnN0IC0gMWU5KSA8IDFlLTQpIGNvbnRpbnVlOwogICAgICAgICAgICBib29sIGJhZCA9IDA7CiAgICAgICAgICAgIGZvcihpbnQgaz0wOyBrPG47IGsrKyl7CiAgICAgICAgICAgICAgICBpZihmdW5jKHZba10sIGNycykgPCAtMWUtNCl7CiAgICAgICAgICAgICAgICAgICAgYmFkID0gMTsKICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBpZighYmFkKSByZXQucHVzaF9iYWNrKGNycyk7CiAgICAgICAgfQogICAgfQogCn0=