largest circle define _CRT_SECURE_NO_WARNI NGS include iostream includ

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
//largest circle//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <iomanip>
#define ll long long
#define eps 1e-8
#define all(x) x.begin(), x.end()
#define Cout cout << fixed << setprecision(6)
const double pi = acos(-1.0);
using namespace std;
int I1 = 38;
int I2 = 38;
struct v2 {
double x, y;
v2() {}
v2(double _x, double _y) : x(_x), y(_y) {}
v2 operator -(const v2 &a) const { return v2(x - a.x, y - a.y); }
v2 operator +(const v2 &a) const { return v2(x + a.x, y + a.y); }
v2 operator *(double a) const { return v2(a * x, a * y); }
inline double sqlen() const { return x * x + y * y; }
bool operator <(const v2 a) const {
if (std::abs(x - a.x) < eps)
return y < a.y;
else
return x < a.x;
}
};
double dot(const v2& a, const v2& b) { return a.x * b.x + a.y * b.y; }
double cross(const v2& a, const v2& b) { return a.x * b.y - a.y * b.x; }
double dist2(const v2&a, const v2& b) { return dot(a - b, a - b); }
double w, h;
vector <v2> g(4);
double dist(const v2& a) {
v2 p = g[0] + (g[3] - g[0]) * (a.x / w);
v2 q = g[1] + (g[2] - g[1]) * (a.x / w);
v2 b = p + (q - p) * (a.y / h);
//Cout << b.x << " " << b.y << endl;
//cout << endl;
return dist2(a, b);
}
double f(double x) {
double l = 0.0, r = h;
for (int q = 0; q < 30; ++q) {
double y1 = l + (r - l) / 3;
double y2 = r - (r - l) / 3;
//Cout << "ololo " << y1 << " " << y2 << endl << dist(v2(x, y1)) << " " << dist(v2(x, y2)) << endl << endl;
if (dist(v2(x, y1)) > dist(v2(x, y2)))
l = y1;
else
r = y2;
}
return dist(v2(x, l));
}
double final_f(double x) {
double l = 0.0, r = h;
for (int q = 0; q < 40; ++q) {
double y1 = l + (r - l) * 0.49;
double y2 = l + (r - l) * 0.51;
if (dist(v2(x, y1)) > dist(v2(x, y2)))
l = y1;
else
r = y2;
}
return l;
}
int main(){
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//freopen( "output.txt", "w", stdout);
#endif
int n;
cin >> w >> h;
for (int i = 0; i < 4; ++i)
cin >> g[i].x >> g[i].y;
double l = 0.0, r = w;
for (int q = 0; q < 40; ++q) {
double x1 = l + (r - l) * 0.49;
double x2 = l + (r - l) * 0.51;
if (f(x1) > f(x2))
l = x1;
else
r = x2;
}
double x = l;
double y = final_f(x);
double ans = dist(v2(x, y));
if (dist(v2(x, y)) < 1e-6)
Cout << x << " " << y << endl;
else
cout << "NONE" << endl;
return 0;
}