QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#345531 | #7734. Intersection over Union | Sorting | TL | 11ms | 3816kb | C++20 | 4.5kb | 2024-03-07 05:28:52 | 2024-03-07 05:28:53 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <stack>
#include <utility>
#include <iomanip>
using namespace std;
typedef double ld;
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
P operator+(P p) const { return P(x+p.x, y+p.y); }
P operator-(P p) const { return P(x-p.x, y-p.y); }
P operator*(T d) const { return P(x*d, y*d); }
P operator/(T d) const { return P(x/d, y/d); }
T dot(P p) const { return x*p.x + y*p.y; }
T cross(P p) const { return x*p.y - y*p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x*x + y*y; }
double dist() const { return sqrt((double)dist2()); }
// angle to x-axis in interval [-pi, pi]
double angle() const { return atan2(y, x); }
P unit() const { return *this/dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const {
return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")"; }
};
typedef Point<ld> P;
template<class T>
T polygonArea2(const vector<Point<T>> &v) {
T a = v.back().cross(v[0]);
for(int i = 0; i < (int)v.size() - 1; ++i) a += v[i].cross(v[i+1]);
return a;
}
pair<int, P> lineInter(P s1, P e1, P s2, P e2) {
auto d = (e1 - s1).cross(e2 - s2);
if (d == 0) // if parallel
return {-(s1.cross(e1, s2) == 0), P(0, 0)};
auto p = s2.cross(e1, e2), q = s2.cross(e2, s1);
return {1, (s1 * p + e1 * q) / d};
}
vector<P> polygonCut(const vector<P>& poly, P s, P e) {
vector<P> res;
for(int i = 0; i < poly.size(); ++i){
P cur = poly[i], prev = i ? poly[i-1] : poly.back();
bool side = s.cross(e, cur) < 0;
if (side != (s.cross(e, prev) < 0))
res.push_back(lineInter(s, e, cur, prev).second);
if (side)
res.push_back(cur);
}
return res;
}
const ld EPS = 1e-9;
P p[4];
P center;
ld area;
vector<P> v;
ld calc(ld x, ld y){
// cout << "calc " << x << " " << y << endl;
vector<P> our;
our.push_back(P{center.x - x, center.y - y});
our.push_back(P{center.x + x, center.y - y});
our.push_back(P{center.x + x, center.y + y});
our.push_back(P{center.x - x, center.y + y});
// cout << center.x << " " << center.y << "\n";
for(int i = 0; i < 4; ++i){
// cout << i << " i" << endl;
int prv = (i + 4 - 1) % 4;
our = polygonCut(our, v[i], v[prv]);
// cout << our.size() << " size here" << endl;
}
// cout << our.size() << " size" << endl;
ld inters_area = abs(polygonArea2(our)) / 2;
ld added_area = 4 * x * y - inters_area;
return inters_area / (added_area + area);
}
ld search_y(ld x){
ld r = (sqrt((ld)5) - 1) / 2;
ld a = 0, b = 2e9;
ld x1 = b - r*(b-a), x2 = a + r*(b-a);
ld f1 = calc(x, x1), f2 = calc(x, x2);
while((b - a) > EPS){
if(f1 > f2){
b = x2; x2 = x1; f2 = f1;
x1 = b - r*(b-a); f1 = calc(x, x1);
} else {
a = x1; x1 = x2; f1 = f2;
x2 = a + r*(b-a); f2 = calc(x, x2);
}
}
return calc(x, a);
}
ld search_x(){
ld r = (sqrt((ld)5) - 1) / 2;
ld a = 0, b = 2e9;
ld x1 = b - r*(b-a), x2 = a + r*(b-a);
ld f1 = search_y(x1), f2 = search_y(x2);
while((b - a) > EPS){
if(f1 > f2){
b = x2; x2 = x1; f2 = f1;
x1 = b - r*(b-a); f1 = search_y(x1);
} else {
a = x1; x1 = x2; f1 = f2;
x2 = a + r*(b-a); f2 = search_y(x2);
}
}
return search_y(a);
}
void solve(){
for(int i = 0; i < 4; ++i){
int x, y;
cin >> x >> y;
p[i] = P{(ld)x, (ld)y};
}
v = vector<P>(p, p + 4);
area = polygonArea2(v);
if(area < 0){
reverse(p, p + 4);
reverse(v.begin(), v.end());
area = -area;
}
area /= 2;
center = (p[0] + p[1] + p[2] + p[3]) / 4;
cout << fixed << setprecision(12) << search_x() << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 3816kb
input:
3 0 2 2 0 0 -2 -2 0 7 -2 9 -2 9 2 7 2 7 13 11 10 5 2 1 5
output:
0.707106781187 0.999999999346 0.623843224831
result:
ok 3 numbers
Test #2:
score: -100
Time Limit Exceeded
input:
10000 -568767734 379152673 -565681345 -54946093 -131582579 -51859704 -134668968 382239062 -194884120 -559906233 -194884142 -158042604 -998611400 -158042648 -998611378 -559906277 459335966 -945199065 478030260 -934243779 450535683 -887326546 431841389 -898281832 -483567491 491964356 -523827401 408140...