Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define _USE_MATH_DEFINES
- #include <iostream>
- #include <string>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <ctime>
- #include <cstring>
- #include <iomanip>
- #include <random>
- #include <unordered_set>
- #include <unordered_map>
- #include <deque>
- #include <queue>
- #include <bitset>
- #include <sstream>
- using namespace std;
- #define mp make_pair
- #define X first
- #define Y second
- #define all(x) x.begin(), x.end()
- #define all_(x) x.rbegin(), x.rend()
- typedef unsigned int ui;
- typedef unsigned long long ll;
- typedef double ld;
- const int INF = 2e9 + 9;
- const int MAXN = 35e3 + 7;
- const ll MOD = 1e9 + 7;
- const ll ST = 157;
- const ll ST1 = 199;
- const ld EPS = 1e-7;
- const int BLOCK = 138;
- void solve();
- signed main(){
- srand('a' + 'l' + 'e' + 'x' + 'X' + '5' + '1' + '2');
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif // _DEBUG
- solve();
- }
- /*--------------------------------------------------------------------------------------------------*/
- ld ans1 = 2 * M_PI;
- struct line{
- ld a, b, c;
- line(pair<ld, ld> q1, pair<ld, ld> q2) : a(q2.Y - q1.Y), b(q1.X - q2.X), c(-a*q1.X - b*q1.Y) {}
- };
- pair<ld, ld> operator -(pair<ld, ld> a, pair<ld, ld> b){
- return mp(a.first - b.first, a.second - b.second);
- }
- pair<ld, ld> operator +(pair<ld, ld> a, pair<ld, ld> b){
- return mp(a.first + b.first, a.second + b.second);
- }
- pair<ld, ld> operator /(pair<ld, ld> a, ld b){
- return mp(a.first / b, a.second / b);
- }
- pair<ld, ld> operator *(pair<ld, ld> a, ld b){
- return mp(a.first * b, a.second * b);
- }
- ld dot(pair<ld, ld> a, pair<ld, ld> b){
- return a.first * b.second - a.second * b.first;
- }
- ld cros(pair<ld, ld> a, pair<ld, ld> b){
- return a.first * b.first + a.second * b.second;
- }
- pair<ld, ld> alf(pair<ld, ld> a, pair<ld, ld> b, pair<ld, ld> st){
- ld t = atan2l(dot(a - st, b - st), cros(a - st, b - st));
- return mp(sinl(t), cosl(t));
- }
- ld len(pair<ld, ld> a){
- return sqrtl(cros(a, a));
- }
- pair<ld, ld> new_cord(pair<ld, ld> a, pair<ld, ld> dop, pair<ld, ld> st){
- pair<ld, ld> c = (a - st), c1 = c;
- c.first = (c1.first * dop.second - c1.second * dop.first);
- c.second = (c1.first * dop.first + c1.second * dop.second);
- return c + st;
- }
- bool eq(pair<ld, ld> a, pair<ld, ld> b){
- return abs(a.first - b.first) < EPS && abs(a.second - b.second) < EPS;
- }
- bool eq(ld a, ld b){
- return abs(a - b) < EPS;
- }
- pair<ld, ld> start(pair<ld, ld> a1, pair<ld, ld> a2, pair<ld, ld> b1, pair<ld, ld> b2){
- auto pa1 = (a1 + a2) / 2.0;
- auto pb1 = (b1 + b2) / 2.0;
- a1 = mp(a1.second, -a1.first);
- a2 = mp(a2.second, -a2.first);
- b1 = mp(b1.second, -b1.first);
- b2 = mp(b2.second, -b2.first);
- auto pa2 = pa1 + a1 - a2;
- auto pb2 = pb1 + b1 - b2;
- if (eq(dot(pa1 - pa2, pb1 - pb2), 0)){
- a1 = mp(-a1.second, a1.first);
- a2 = mp(-a2.second, a2.first);
- b1 = mp(-b1.second, b1.first);
- b2 = mp(-b2.second, b2.first);
- if (eq(dot(a1 - b1, a2 - b2), 0)){
- if (eq(dot(a1 - b1, a2 - b1), 0)){
- return (max({ a1, a2, b1, b2 }) + min({ a1, a2, b1, b2 })) / 2.0;
- }
- return mp(INF, INF);
- }
- line q1(a1, b1), q2(a2, b2);
- return mp((q1.b * q2.c - q2.b * q1.c) / (q1.a * q2.b - q2.a * q1.b), (q1.a * q2.c - q2.a * q1.c) / (q1.a * q2.b - q2.a * q1.b));
- }
- line q1(pa1, pa2), q2(pb1, pb2);
- return mp((q1.b * q2.c - q2.b * q1.c) / (q1.a * q2.b - q2.a * q1.b), (q1.a * q2.c - q2.a * q1.c) / (q1.a * q2.b - q2.a * q1.b));
- }
- void get(int n, pair<ld, ld> st, pair<ld, ld> a, vector<pair<ld, ld>> &v1, vector<pair<ld, ld>> &v2){
- for (int j = 1; j < n; j++){
- auto now = new_cord(v1[j], a, st);
- bool b = 1;
- for (int i = 0; i < n && b; i++){
- if (eq(now, v2[i])){
- b = 0;
- }
- }
- if(!b){
- if (j == n - 1){
- ld ans = atan2(a.first, a.second);
- if (ans < 0){
- ans += 2 * M_PI;
- }
- ans1 = min(ans1, ans);
- }
- continue;
- }
- break;
- }
- }
- void solve(){
- int n;
- cin >> n;
- vector<pair<ld, ld>> v1(n), v2(n);
- for (auto &i : v1){
- cin >> i.first >> i.second;
- }
- for (auto &i : v2){
- cin >> i.first >> i.second;
- }
- sort(all(v2));
- for (int i = 0; i < n; i++){
- for (int j = 0; j < n; j++){
- if (eq(len(v2[i] - v2[j]), len(v1[0] - v1[1]))){
- auto t = start(v1[0], v2[i], v1[1], v2[j]);
- auto p = alf(v1[0], v2[i], t);
- if (v1[0] == v2[i]) p = alf(v1[1], v2[j], t);
- if(!eq(t,mp(INF, INF))) get(n, t, p, v1, v2);
- t = start(v1[0], v2[j], v1[1], v2[i]);
- p = alf(v1[0], v2[j], t);
- if (v1[0] == v2[j]) p = alf(v1[1], v2[i], t);
- if (!eq(t, mp(INF, INF))) get(n, t, p, v1, v2);
- }
- }
- }
- cout << fixed << setprecision(6) << ans1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement