이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "nice_lines.h"
#include <bits/stdc++.h>
using namespace std;
template<class T>
struct Point{
T x, y;
Point (T _x=0, T _y=0){
x=_x; y=_y;
}
bool operator<(Point a){ return tie(x, y)<tie(a.x, a.y); }
bool operator==(Point a){ return tie(x, y)==tie(a.x, a.y); }
Point operator+(Point a){ return Point(x+a.x, y+a.y); }
Point operator-(Point a){ return Point(x-a.x, y-a.y); }
Point operator*(T a){ return Point(x*a, y*a); }
Point operator/(T a){ return Point(x/a, y/a); }
T dot(Point a){ return x*a.x+y*a.y; }
T dot(Point a, Point b){ return (a-*this).dot(b-*this); }
T cross(Point a){ return x*a.y-y*a.x; }
T cross(Point a, Point b){ return (a-*this).cross(b-*this); }
T dist2(){ return x*x+y*y; }
long double dist(){ return sqrt(dist2()); }
};
const long double eps=1e-5;
using pt=Point<long double>;
long double line_point_dist(pt a, pt b, pt c){
return abs(a.cross(b, c))/(a-b).dist();
}
mt19937 rng(69420);
long double rand(long double l, long double r){
return uniform_real_distribution<long double>(l, r)(rng);
}
pair<int, int> line_from_points(pt a, pt b){
long double slope=round((b.y-a.y)/(b.x-a.x));
return {(int)(round(slope)), (int)(round(a.y-a.x*slope))};
}
void solve(int subtask_id, int N) {
if (N==1){
pt a, b;
{
pt l(-1e12, -rand(0, 69420));
pt r(1e12, rand(0, 69420));
for (int _=0; _<125; ++_){
pt m1=l+(r-l)/3, m2=l+(r-l)/3*2;
long double t1=query(m1.x, m1.y), t2=query(m2.x, m2.y);
if (t1<t2) r=m2;
else l=m1;
}
a=l;
}
{
pt l(-rand(0, 69420), -1e12);
pt r(rand(0, 69420), 1e12);
for (int _=0; _<125; ++_){
pt m1=l+(r-l)/3, m2=l+(r-l)/3*2;
long double t1=query(m1.x, m1.y), t2=query(m2.x, m2.y);
if (t1<t2) r=m2;
else l=m1;
}
b=l;
}
auto line=line_from_points(a, b);
the_lines_are({line.first}, {line.second});
return;
}
if (N==2){
vector<pt> v;
for (int i=1; i<=10; ++i){
pt l(-1e12, -rand(0, 69420));
pt r(1e12, rand(0, 69420));
for (int _=0; _<125; ++_){
pt m1=l+(r-l)/3, m2=l+(r-l)/3*2;
long double t1=query(m1.x, m1.y), t2=query(m2.x, m2.y);
if (t1<t2) r=m2;
else l=m1;
}
v.push_back(l);
}
for (int i=1; i<=10; ++i){
pt l(-1e12, rand(0, 69420));
pt r(1e12, -rand(0, 69420));
for (int _=0; _<125; ++_){
pt m1=l+(r-l)/3, m2=l+(r-l)/3*2;
long double t1=query(m1.x, m1.y), t2=query(m2.x, m2.y);
if (t1<t2) r=m2;
else l=m1;
}
v.push_back(l);
}
for (int i=1; i<=10; ++i){
pt l(-rand(0, 69420), -1e12);
pt r(rand(0, 69420), 1e12);
for (int _=0; _<125; ++_){
pt m1=l+(r-l)/3, m2=l+(r-l)/3*2;
long double t1=query(m1.x, m1.y), t2=query(m2.x, m2.y);
if (t1<t2) r=m2;
else l=m1;
}
v.push_back(l);
}
for (int i=1; i<=10; ++i){
pt l(rand(0, 69420), -1e12);
pt r(-rand(0, 69420), 1e12);
for (int _=0; _<125; ++_){
pt m1=l+(r-l)/3, m2=l+(r-l)/3*2;
long double t1=query(m1.x, m1.y), t2=query(m2.x, m2.y);
if (t1<t2) r=m2;
else l=m1;
}
v.push_back(l);
}
for (int i=0; i<2; ++i) for (int j=i+1; j<2; ++j){
vector<pt> v1, v2;
for (int k=0; k<(int)v.size(); ++k){
if (abs(v[i].cross(v[j], v[k]))<eps){
v1.push_back(v[k]);
}else{
v2.push_back(v[k]);
}
}
if ((int)v1.size()<2 || (int)v2.size()<2) continue;
bool check=1;
for (int k=0; k<(int)v2.size(); ++k) check&=abs(v2[0].cross(v2[1], v2[k]))<eps;
if (!check) continue;
auto line1=line_from_points(v1[0], v1[1]);
auto line2=line_from_points(v2[0], v2[1]);
the_lines_are({line1.first, line2.first}, {line1.second, line2.second});
return;
}
assert(false);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |