求助P8008 wdoi的迷途竹林
  • 板块题目总版
  • 楼主Joseph_H
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/1/24 10:43
  • 上次更新2023/10/28 11:21:12
查看原帖
求助P8008 wdoi的迷途竹林
568775
Joseph_H楼主2022/1/24 10:43
#include<bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-6;
const int maxp = 10010;
int sgn(double x){
	if(fabs(x) < eps) return 0;
	else return x < 0 ? -1 : 1;
}
int Dcmp(double x,double y){
	if(fabs(x - y) < eps) return 0;
	else return x > y ? -1 : 1;
}
struct Point{
	double x,y;
	Point(){
		
	}
	Point(double x,double y):x(x),y(y){
		
	}
	Point operator + (Point B){
		return Point(x + B.x,y + B.y);
	}
	Point operator - (Point B){
		return Point(x - B.x,y - B.y);
	}
	Point operator * (double k){
		return Point(x * k,y * k);
	}
	Point operator / (double k){
		return Point(x / k,y / k);
	}
	bool operator == (Point B){
		return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;
	}
	bool operator < (const Point B)const {
		return sgn(x - B.x) < 0 || (sgn(x - B.x) == 0 && sgn(y - B.y) < 0);
	}
};
typedef Point Vector;
double Dot(Vector A,Vector B){
	return A.x * B.x + A.y * B.y;
}
double Len(Vector A){
	return sqrt(Dot(A,A));
} 
double Len2(Vector A){
	return Dot(A,A);
}
double Angle(Vector A,Vector B){
	return acos(Dot(A,B)/Len(A)/Len(B));
}
double Cross(Vector A,Vector B){
	return A.x * B.y - A.y * B.x;
}
double Area2(Point A,Point B,Point C){
	return Cross(B - A,C - A);
}
double Distance(Point A,Point B){
	return hypot(A.x - B.x,A.y - B.y);
}
double Dist(Point A,Point B){
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
Vector Normal(Vector A){
	return Vector(-A.y / Len(A),A.x / Len(A));
}
bool Parallel(Vector A,Vector B){
	return sgn(Cross(A,B)) == 0;
}
Vector Rotate(Vector A,double rad){
	return Vector(A.x * cos(rad) - A.y * sin(rad),A.x * sin(rad) + A.y * cos(rad));
}
struct Line{
	Point p1,p2;
	Line(){
		
	}
	Line(Point p1,Point p2):p1(p1),p2(p2){
		
	}
	Line(Point p,double angle){
		p1 = p;
		if(!sgn(angle - pi / 2)){
			p2 = (p1 + Point(0,1));
		}
		else {
			p2 = (p1 + Point(1,tan(angle)));
		}
	}
	Line(double a,double b,double c){
		if(!sgn(a)){
			p1 = Point(0,- c / b);
			p2 = Point(1,- c / b);
		}
		else if(!sgn(b)){
			p1 = Point(- c / a,0);
			p2 = Point(- c / a,1);
		}
		else if(!sgn(c)){
			p1 = Point(0,- c / b);
			p2 = Point(1,(- c - a) / b);
		}
	}
};
typedef Line Segment;
double Line_angle(Line v){
	double k = atan2(v.p2.y - v.p1.y,v.p2.x - v.p1.x);
	if(sgn(k) < 0){
		k += pi;
	}
	if(!sgn(k)){
		k -= pi;
	}
	return k;
}
int Point_line_relation(Point p,Line v){
	int c = sgn(Cross(p - v.p1,v.p2 - v.p1));
	if(c < 0) return 1;
	if(c > 0) return 2;
	return 0;
}
bool Point_on_seg(Point p,Line v){
	return !sgn(Cross(p - v.p1,v.p2 - v.p1)) && sgn(Dot(p - v.p1,v.p1 - v.p2)) <= 0;
}
int Line_relation(Line v1,Line v2){
	if(!sgn(Cross(v1.p2 - v1.p1,v2.p2 - v2.p1))){
		if(!Point_line_relation(v1.p1,v2)) return 1;
		else return 0;
	}
	return 2;
}
double Dis_point_line(Point p,Line v){
	return fabs(Cross(p - v.p1,v.p2 - v.p1)) / Distance(v.p1,v.p2);
}
Point Point_line_proj(Point p,Line v){
	double k = Dot(v.p2 - v.p1,p - v.p1) / Len2(v.p2 - v.p1);
	return v.p1 + (v.p2 - v.p1) * k;
}
Point Point_line_symmetry(Point p,Line v){
	Point q = Point_line_proj(p,v);
	return Point(2 * q.x - p.x,2 * q.y - p.y);
}
double Dis_point_seg(Point p,Segment v){
	if(sgn(Dot(p - v.p1,v.p2 - v.p1)) < 0 || sgn(Dot(p - v.p2,v.p1 - v.p2)) < 0){
		return min(Distance(p,v.p1),Distance(p,v.p2));
	}
	return Dis_point_line(p,v);
}
Point Cross_point(Point a,Point b,Point c,Point d){
	double s1 = Cross(b - a,c - a);
	double s2 = Cross(b - a,d - a);
	return Point(c.x * s2 - d.x * s1,c.y * s2 - d.y * s1) / (s2 - s1);
}
bool Cross_segment(Point a,Point b,Point c,Point d){
	double c1 = Cross(b - a,c - a),c2 = Cross(b - a,d - a);
	double d1 = Cross(d - c,a - c),d2 = Cross(d - c,b - c);
	return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0;
}
struct Polygon{
	int n;
	Point p[maxp];
	Line v[maxp];
}; 
int Point_in_polygon(Point pt,Point *p,int n){
	for(int i = 0;i < n;i++){
		if(p[i] == pt) return 3;
	}
	for(int i = 0;i < n;i++){
		Line v = Line(p[i],p[(i + 1) % n]);
		if(Point_on_seg(pt,v)) return 2;
	}
	int num = 0;
	for(int i = 0;i < n;i++){
		int j = (i + 1) % n;
		int c = sgn(Cross(pt - p[j],p[i] - p[j]));
		int u = sgn(p[i].y - pt.y);
		int v = sgn(p[j].y - pt.y);
		if(c > 0 && u < 0 && v >= 0) num++;
		if(c < 0 && u >= 0 && v < 0) num--;
	}
	return num != 0;
}
double Polygon_area(Point *p,int n){
	double area = 0;
	for(int i = 0;i < n;i++){
		area += Cross(p[i],p[(i + 1) % n]);
	}
	return area / 2;
}
Point Polygon_center(Point *p,int n){
	Point ans(0,0);
	if(!Polygon_area(p,n)) return ans;
	for(int i = 0;i < n;i++){
		ans = ans + (p[i] + p[(i + 1) % n] * Cross(p[i],p[(i + 1) % n]));
	}
	return ans / Polygon_area(p,n) / 6;
}
int Convex_hull(Point *p,int n,Point *ch){
	stable_sort (p,p + n);
	n = unique(p,p + n) - p;
	int v = 0;
	for(int i = 0;i < n;i++){
		while(v > 1 && sgn(Cross(ch[v - 1] - ch[v - 2],p[i] - ch[v - 2])) <= 0){
			v--;
		}
		ch[v++] = p[i];
	}
	int j = v;
	for(int i = n - 2;i >= 0;i--){
		while(v > j && sgn(Cross(ch[v - 1] - ch[v - 2],p[i] - ch[v - 2])) <= 0){
			v--;
		}
		ch[v++] = p[i];
	}
	if(n > 1) v--;
	return v;
}
int n;
double k;
int a;
Polygon p;
int minn = 0x7fffffff,maxn = -0x7fffffff;
Point minn_p,maxn_p;
Line Line_x = Line(Point(-1,0),Point(1,0));
Line Line_y = Line(Point(0,-1),Point(0,1));
Polygon gets(){
	scanf("%d",&n);
	Polygon pp;
	for(int i = 1;i <= n;i++){
		double a,b;
		scanf("%lf%lf",&a,&b);
		pp.p[i] = Point(a,b);
	}
	scanf("%lf%lf",&k,&a);
	for(int i = 1;i <= n;i++){
		Line l = Line(pp.p[i],k);
		Point p1 = Cross_point(l.p1,l.p2,Line_x.p1,Line_x.p2); 
		if(p1.x < minn){
			minn = p1.x;
			minn_p = pp.p[i];
		}
		if(p1.x > maxn){
			maxn = p1.x;
			maxn_p = pp.p[i];
		}
	}
	for(int i = 1;i <= n;i++){
		pp.v[i] = Segment(pp.p[i],pp.p[i % n + 1]);
	}
	return pp;
}

int main(){
	p = gets();
	Line min_L = Line(minn_p,k);
	Line max_L = Line(maxn_p,k);
	Point p_min = Cross_point(Line_x.p1,Line_x.p2,min_L.p1,min_L.p2);
	Point p_max = Cross_point(Line_x.p1,Line_x.p2,max_L.p1,max_L.p2);
	int cnt = 0;
	double ans = 0;
	while(p_max.x > a * cnt || -a * cnt > p_min.x){
		Point p1 = Point(cnt * a,0);
		Point p2 = Point(-cnt * a,0);
		Line l1 = Line(p1,k);
		Line l2 = Line(p2,k);
		vector <Point> vp1,vp2;
		for(int i = 1;i <= n;i++){
			if(Cross_segment(l1.p1,l1.p2,Line_x.p1,Line_x.p2));
				vp1.push_back(Cross_point(l1.p1,l1.p2,Line_x.p1,Line_x.p2));
			if(Cross_segment(l2.p1,l2.p2,Line_x.p1,Line_x.p2));
				vp2.push_back(Cross_point(l2.p1,l2.p2,Line_x.p1,Line_x.p2));
		}
		stable_sort(vp1.begin(),vp1.end());
		stable_sort(vp2.begin(),vp2.end());
		for(int i = 0;i < vp1.size();i += 2){
			ans += Distance(vp1[i],vp1[i + 1]);
		}
		if(cnt != 0)
			for(int i = 0;i < vp2.size();i += 2){
				ans += Distance(vp2[i],vp2[i + 1]);
			}
		cnt++;
	}
	printf("%lf",ans);
}

求求了,孩子改了两三天了还是不会(艹)

题目链接

2022/1/24 10:43
加载中...