2019 서북공업대학 프로그램 설계 혁신 실천기지 봄 선발전(재현전)
귀찮아서 그냥 Kuangbin 크게 붙여버렸어요.마지막으로 정돈하여 정밀도 손실을 더했다
#include
", x, y);
}
bool operator == (Point b)const{
return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
}
bool operator < (Point b)const{
return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
}
Point operator-(const Point &b)const{
return Point(x - b.x, y - b.y);
}
//
double operator ^(const Point &b)const{
return x*b.y - y*b.x;
}
//
double operator *(const Point &b)const{
return x*b.x + y*b.y;
}
//
double len(){
return hypot(x, y);//
}
//
double len2(){
return x*x + y*y;
}
//
double distance(Point p){
return hypot(x - p.x, y - p.y);
}
Point operator +(const Point &b)const{
return Point(x + b.x, y + b.y);
}
Point operator *(const double &k)const{
return Point(x*k, y*k);
}
Point operator /(const double &k)const{
return Point(x / k, y / k);
}
// pa pb
// a,b
// LightOJ1203
double rad(Point a, Point b){
Point p = *this;
return fabs(atan2(fabs((a - p) ^ (b - p)), (a - p)*(b - p)));
}
// r
Point trunc(double r){
double l = len();
if (!sgn(l))return *this;
r /= l;
return Point(x*r, y*r);
}
// 90
Point rotleft(){
return Point(-y, x);
}
// 90
Point rotright(){
return Point(y, -x);
}
// p angle
Point rotate(Point p, double angle){
Point v = (*this) - p;
double c = cos(angle), s = sin(angle);
return Point(p.x + v.x*c - v.y*s, p.y + v.x*s + v.y*c);
}
};
/*
* Stores two points
* Line()-Empty constructor
* Line(Point _s,Point _e)-Line through _s and _e
* operator ==-checks if two points are same
* Line(Point p,double angle)-one end p , another end at
angle degree
* Line(double a,double b,double c)-Line of equation ax + by + c
= 0
* input()-inputs s and e
* adjust()-orders in such a way that s < e
* length()-distance of se
* angle()-return 0 <= angle < pi
* relation(Point p)-3 if point is on line
* 1 if point on the left of line
* 2 if point on the right of line
* pointonseg(double p)-return true if point on segment
* parallel(Line v)-return true if they are
parallel
* segcrossseg(Line v)-returns 0 if does not intersect
* returns 1 if non-standard
intersection
* returns 2 if intersects
* linecrossseg(Line v)-line and seg
* linecrossline(Line v)-0 if parallel
* 1 if coincides
* 2 if intersects
* crosspoint(Line v)-returns intersection point
* dispointtoline(Point p)-distance from point p to the
line
* dispointtoseg(Point p)-distance from p to the segment
* dissegtoseg(Line v)-distance of two segment
* lineprog(Point p)-returns projected point p on se
line
* symmetrypoint(Point p)-returns reflection point of p
over se
*
*/
struct Line{
Point s, e;
Line(){}
Line(Point _s, Point _e){
s = _s;
e = _e;
}
bool operator ==(Line v){
return (s == v.s) && (e == v.e);
}
// angle ,0<=angle
Line(Point p, double angle){
s = p;
if (sgn(angle - pi / 2) == 0){
e = (s + Point(0, 1));
}
else{
e = (s + Point(1, tan(angle)));
}
}
//ax+by+c=0
Line(double a, double b, double c){
if (sgn(a) == 0){
s = Point(0, -c / b);
e = Point(1, -c / b);
}
else if (sgn(b) == 0){
s = Point(-c / a, 0);
e = Point(-c / a, 1);
}
else{
s = Point(0, -c / b);
e = Point(1, (-c - a) / b);
}
}
void input(){
s.input();
e.input();
}
void adjust(){
if (e < s)swap(s, e);
}
//
double length(){
return s.distance(e);
}
// 0<=angle
double angle(){
double k = atan2(e.y - s.y, e.x - s.x);
if (sgn(k) < 0)k += pi;
if (sgn(k - pi) == 0)k -= pi;
return k;
}
//
//1
//2
//3
int relation(Point p){
int c = sgn((p - s) ^ (e - s));
if (c < 0)return 1;
else if (c > 0)return 2;
else return 3;
}
//
bool pointonseg(Point p){
return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s)*(p - e)) <= 0;
}
// ( )
bool parallel(Line v){
return sgn((e - s) ^ (v.e - v.s)) == 0;
}
//
//2
//1
//0
int segcrossseg(Line v){
int d1 = sgn((e - s) ^ (v.s - s));
int d2 = sgn((e - s) ^ (v.e - s));
int d3 = sgn((v.e - v.s) ^ (s - v.s));
int d4 = sgn((v.e - v.s) ^ (e - v.s));
if ((d1^d2) == -2 && (d3^d4) == -2)return 2;
return (d1 == 0 && sgn((v.s - s)*(v.s - e)) <= 0) ||
(d2 == 0 && sgn((v.e - s)*(v.e - e)) <= 0) ||
(d3 == 0 && sgn((s - v.s)*(s - v.e)) <= 0) ||
(d4 == 0 && sgn((e - v.s)*(e - v.e)) <= 0);
}
//
//-*this line -v seg
//2
//1
//0
int linecrossseg(Line v){
int d1 = sgn((e - s) ^ (v.s - s));
int d2 = sgn((e - s) ^ (v.e - s));
if ((d1^d2) == -2) return 2;
return (d1 == 0 || d2 == 0);
}
//
//0
//1
//2
int linecrossline(Line v){
if ((*this).parallel(v))
return v.relation(s) == 3;
return 2;
}
//
//
Point crosspoint(Line v){
double a1 = (v.e - v.s) ^ (s - v.s);
double a2 = (v.e - v.s) ^ (e - v.s);
return Point((s.x*a2 - e.x*a1) / (a2 - a1), (s.y*a2 - e.y*a1) / (a2 - a1
));
}
//
double dispointtoline(Point p){
return fabs((p - s) ^ (e - s)) / length();
}
//
double dispointtoseg(Point p){
if (sgn((p - s)*(e - s)) < 0 || sgn((p - e)*(s - e)) < 0)
return min(p.distance(s), p.distance(e));
return dispointtoline(p);
}
//
// ， 0
double dissegtoseg(Line v){
return min(min(dispointtoseg(v.s), dispointtoseg(v.e)), min(v
.dispointtoseg(s), v.dispointtoseg(e)));
}
// p
Point lineprog(Point p){
return s + (((e - s)*((e - s)*(p - s))) / ((e - s).len2()));
}
// p
Point symmetrypoint(Point p){
Point q = lineprog(p);
return Point(2 * q.x - p.x, 2 * q.y - p.y);
}
};
//
struct circle{
Point p;//
double r;//
circle(){}
circle(Point _p, double _r){
p = _p;
r = _r;
}
circle(double x, double y, double _r){
p = Point(x, y);
r = _r;
}
//
// Point + / rotate() Line crosspoint()
//
// ：UVA12304
circle(Point a, Point b, Point c){
Line u = Line((a + b) / 2, ((a + b) / 2) + ((b - a).rotleft()));
Line v = Line((b + c) / 2, ((b + c) / 2) + ((c - b).rotleft()));
p = u.crosspoint(v);
r = p.distance(a);
}
//
// bool t ，
// ：UVA12304
circle(Point a, Point b, Point c, bool t){
Line u, v;
double m = atan2(b.y - a.y, b.x - a.x), n = atan2(c.y - a.y, c.x - a.
x);
u.s = a;
u.e = u.s + Point(cos((n + m) / 2), sin((n + m) / 2));
v.s = b;
m = atan2(a.y - b.y, a.x - b.x), n = atan2(c.y - b.y, c.x - b.x);
v.e = v.s + Point(cos((n + m) / 2), sin((n + m) / 2));
p = u.crosspoint(v);
r = Line(a, b).dispointtoseg(p);
}
//
void input(){
p.input();
scanf("%lf", &r);
}
//
void output(){
printf("%.2lf?%.2lf?%.2lf
", p.x, p.y, r);
}
bool operator == (circle v){
return (p == v.p) && sgn(r - v.r) == 0;
}
bool operator < (circle v)const{
return ((p < v.p) || ((p == v.p) && sgn(r - v.r) < 0));
}
//
double area(){
return pi*r*r;
}
//
double circumference(){
return 2 * pi*r;
}
//
//0
//1
//2
int relation(Point b){
double dst = b.distance(p);
if (sgn(dst - r) < 0)return 2;
else if (sgn(dst - r) == 0)return 1;
return 0;
}
//
//
int relationseg(Line v){
double dst = v.dispointtoseg(p);
if (sgn(dst - r) < 0)return 2;
else if (sgn(dst - r) == 0)return 1;
return 0;
}
//
//
int relationline(Line v){
double dst = v.dispointtoline(p);
if (sgn(dst - r) < 0)return 2;
else if (sgn(dst - r) == 0)return 1;
return 0;
}
//
//5
//4
//3
//2
//1
// Point distance
// ：UVA12304
int relationcircle(circle v){
double d = p.distance(v.p);
if (sgn(d - r - v.r) > 0)return 5;
if (sgn(d - r - v.r) == 0)return 4;
double l = fabs(r - v.r);
if (sgn(d - r - v.r) < 0 && sgn(d - l) > 0)return 3;
if (sgn(d - l) == 0)return 2;
if (sgn(d - l) < 0)return 1;
return 0;
}
// ， 0 ， 1 ，2
// relationcircle
// ：UVA12304
int pointcrosscircle(circle v, Point &p1, Point &p2){
int rel = relationcircle(v);
if (rel == 1 || rel == 5)return 0;
double d = p.distance(v.p);
double l = (d*d + r*r - v.r*v.r) / (2 * d);
double h = sqrt(r*r - l*l);
Point tmp = p + (v.p - p).trunc(l);
p1 = tmp + ((v.p - p).rotleft().trunc(h));
p2 = tmp + ((v.p - p).rotright().trunc(h));
if (rel == 2 || rel == 4)
return 1;
return 2;
}
// ，
int pointcrossline(Line v, Point &p1, Point &p2){
if (!(*this).relationline(v))return 0;
Point a = v.lineprog(p);
double d = v.dispointtoline(p);
d = sqrt(r*r - d*d);
if (sgn(d) == 0){
p1 = a;
p2 = a;
return 1;
}
p1 = a + (v.e - v.s).trunc(d);
p2 = a - (v.e - v.s).trunc(d);
return 2;
}
// a,b ， r1
int gercircle(Point a, Point b, double r1, circle &c1, circle &c2){
circle x(a, r1), y(b, r1);
int t = x.pointcrosscircle(y, c1.p, c2.p);
if (!t)return 0;
c1.r = c2.r = r;
return t;
}
// u ， q, r1
// ：UVA12304
int getcircle(Line u, Point q, double r1, circle &c1, circle &c2){
double dis = u.dispointtoline(q);
if (sgn(dis - r1 * 2) > 0)return 0;
if (sgn(dis) == 0){
c1.p = q + ((u.e - u.s).rotleft().trunc(r1));
c2.p = q + ((u.e - u.s).rotright().trunc(r1));
c1.r = c2.r = r1;
return 2;
}
Line u1 = Line((u.s + (u.e - u.s).rotleft().trunc(r1)), (u.e +
(u.e - u.s).rotleft().trunc(r1)));
Line u2 = Line((u.s + (u.e - u.s).rotright().trunc(r1)), (u.e
+ (u.e - u.s).rotright().trunc(r1)));
circle cc = circle(q, r1);
Point p1, p2;
if (!cc.pointcrossline(u1, p1, p2))cc.pointcrossline(u2, p1, p2)
;
c1 = circle(p1, r1);
if (p1 == p2){
c2 = c1;
return 1;
}
c2 = circle(p2, r1);
return 2;
}
// u,v ， r1
// ：UVA12304
int getcircle(Line u, Line v, double r1, circle &c1, circle &c2,
circle &c3, circle &c4){
if (u.parallel(v))return 0;//
Line u1 = Line(u.s + (u.e - u.s).rotleft().trunc(r1), u.e + (u
.e - u.s).rotleft().trunc(r1));
Line u2 = Line(u.s + (u.e - u.s).rotright().trunc(r1), u.e + (
u.e - u.s).rotright().trunc(r1));
Line v1 = Line(v.s + (v.e - v.s).rotleft().trunc(r1), v.e + (v
.e - v.s).rotleft().trunc(r1));
Line v2 = Line(v.s + (v.e - v.s).rotright().trunc(r1), v.e + (
v.e - v.s).rotright().trunc(r1));
c1.r = c2.r = c3.r = c4.r = r1;
c1.p = u1.crosspoint(v1);
c2.p = u1.crosspoint(v2);
c3.p = u2.crosspoint(v1);
c4.p = u2.crosspoint(v2);
return 4;
}
// cx,cy ， r1
// ：UVA12304
int getcircle(circle cx, circle cy, double r1, circle &c1, circle &
c2){
circle x(cx.p, r1 + cx.r), y(cy.p, r1 + cy.r);
int t = x.pointcrosscircle(y, c1.p, c2.p);
if (!t)return 0;
c1.r = c2.r = r1;
return t;
}
// ( )
// ：UVA12304
int tangentline(Point q, Line &u, Line &v){
int x = relation(q);
if (x == 2)return 0;
if (x == 1){
u = Line(q, q + (q - p).rotleft());
v = u;
return 1;
}
double d = p.distance(q);
double l = r*r / d;
double h = sqrt(r*r - l*l);
u = Line(q, p + ((q - p).trunc(l) + (q - p).rotleft().trunc(h)))
;
v = Line(q, p + ((q - p).trunc(l) + (q - p).rotright().trunc(h))
);
return 2;
}
//
double areacircle(circle v){
int rel = relationcircle(v);
if (rel >= 4)return 0.0;
if (rel <= 2)return min(area(), v.area());
double d = p.distance(v.p);
double hf = (r + v.r + d) / 2.0;
double ss = 2 * sqrt(hf*(hf - r)*(hf - v.r)*(hf - d));
double a1 = acos((r*r + d*d - v.r*v.r) / (2.0*r*d));
a1 = a1*r*r;
double a2 = acos((v.r*v.r + d*d - r*r) / (2.0*v.r*d));
a2 = a2*v.r*v.r;
return a1 + a2 - ss;
}
// pab
// ：POJ3675 HDU3982 HDU2892
double areatriangle(Point a, Point b){
if (sgn((p - a) ^ (p - b)) == 0)return 0.0;
Point q[5];
int len = 0;
q[len++] = a;
Line l(a, b);
Point p1, p2;
if (pointcrossline(l, q[1], q[2]) == 2){
if (sgn((a - q[1])*(b - q[1])) < 0)q[len++] = q[1];
if (sgn((a - q[2])*(b - q[2])) < 0)q[len++] = q[2];
}
q[len++] = b;
if (len == 4 && sgn((q[0] - q[1])*(q[2] - q[1])) > 0)swap(q[1], q
[2]);
double res = 0;
for (int i = 0; i < len - 1; i++){
if (relation(q[i]) == 0 || relation(q[i + 1]) == 0){
double arg = p.rad(q[i], q[i + 1]);
res += r*r*arg / 2.0;
}
else{
res += fabs((q[i] - p) ^ (q[i + 1] - p)) / 2.0;
}
}
return res;
}
};
int main()
{
#ifdef LOCAL
freopen("C:/input.txt", "r", stdin);
#endif
int cx, cy, r, x1, y1, y2;
cin >> cx >> cy >> r >> x1 >> y1 >> y2;
Point A(cx, cy), B(x1, y1), C(0, y2);
circle cir(A, r);
Line L(B, C);
Point D, E;
cir.pointcrossline(L, D, E);
//cout << B.distance(D) << endl;
//cout << B.distance(E) << endl;
ll ans = B.distance(D) * B.distance(E) + 1e-6;
cout << ans << endl;
return 0;
}
B Chino with Repeater
#include C Chino with Queue
f[i][j]팀의 끝을 i로 하여금 이미 배정된 상태를 j로 하는 대가로 먼저 모든 사람을 단독으로 첫 번째 대가로 계산한다.모든 상태를 열거하고 현재 i가 j가 없으면 i를 j의 뒤에 배치하고 해당하는 편안도를 더해서 max를 취하려고 시도합니다.
#include D Chino with Equation
#include
", C(n - 1, m - 1), C(n - 1 + m, m - 1));
return 0;
}
F Chino with Expectation
#include
", res);
}
return 0;
}
G Chino with Train to the Rabbit Town
욕심 전략은 k와 다른 부분을 구성할 수 있다면 그를 한 조로 만들고 그 다음에 계속 일치하게 한다.변수 x를 사용하여 이차 또는 접두사와 나타나는 값을 맵에 끊임없이 삽입하고 x이차 또는 상k를 기록합니다. 맵에서 찾을 수 있다면 이전의 어느 위치에서 시작해서 현재의 위치가 이차 또는 상k임을 설명합니다.
#include H Chino with Ciste
제목은 회전 횟수가 가장 적고 종점에 도달하며 회전 횟수를 출력해야 한다.패스가 가장 짧다고 해서 가장 적게 회전하는 것은 아니기 때문에 일반 BFS를 직접 사용해서는 해답을 구할 수 없습니다.이동할 때 정책을 추가합니다. 현재 i 방향으로 이동하면 벽에 부딪히거나 경계를 벗어날 때까지 계속 이동하고 경로에 접근하지 않은 노드를 입대하고 방향을 추가합니다.각 입대 노드는 현재 노드에서 방향을 바꾸려는 시도를 나타낸다.가장 먼저 모든 위치에 도착하는 경로는 반드시 가장 적게 방향을 바꿔야 한다.
#include
", res);
else
printf("troil
");
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
길 잃은 HYSBZ - 1297dp 매트릭스 최적화문제풀이 구한 시간 t가 너무 커서 직접 밀어내는 방식을 사용할 수 없기 때문에 매트릭스 스피드 幂를 사용하여 택배 밀어내는 속도의 복잡도를 O(n*10)^3logt)로 낮추어 d[code(i,j)]로 i초 전 j노...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
