题目链接 https://codeforces.com/gym/101917
E
题意：给定一个多边形（n个点），然后逆时针旋转A度，然后对多边形进行规约，每个点的x规约到[0,w]范围内，y规约到[0,h]范围内，输出规约后的结果。
解析：求出来 多边形的长和宽，再和w,h比较，对点按比例进行缩放就好了。 （多边形旋转其实是绕给出的第一个点旋转,以为是绕原点wa了1发）。
AC代码
#include <bits/stdc++.h>
#define Vector Point
using namespace std;
typedef long long ll;
const double eps = 1e-;
const double PI=acos(-);
const int maxn = 1e5+,inf=0x3f3f3f3f;
//head-------------------------------------------------------------------
int dcmp(double x) { return fabs(x) < eps ? : (x < ? - : ); }
struct Point {
double x, y; Point(const Point& rhs): x(rhs.x), y(rhs.y) { } //拷贝构造函数
Point(double x = 0.0, double y = 0.0): x(x), y(y) { } //构造函数 friend istream& operator >> (istream& in, Point& P) { return in >> P.x >> P.y; }
friend ostream& operator << (ostream& out, const Point& P) { return out << P.x << ' ' << P.y; } friend Vector operator + (const Vector& A, const Vector& B) { return Vector(A.x+B.x, A.y+B.y); }
friend Vector operator - (const Point& A, const Point& B) { return Vector(A.x-B.x, A.y-B.y); }
friend Vector operator * (const Vector& A, const double& p) { return Vector(A.x*p, A.y*p); }
friend Vector operator / (const Vector& A, const double& p) { return Vector(A.x/p, A.y/p); }
friend bool operator == (const Point& A, const Point& B) { return dcmp(A.x-B.x) == && dcmp(A.y-B.y) == ; }
friend bool operator < (const Point& A, const Point& B) { return dcmp(A.x - B.x)< || (dcmp(A.x - B.x)== && dcmp(A.y - B.y)<); }
void in() { scanf("%lf%lf", &x, &y); }
void out() { printf("%.10f %.10f\n", x, y); }
}; template <class T> T sqr(T x) { return x * x;}
double Dot(const Vector& A, const Vector& B) { return A.x*B.x + A.y*B.y; } //点积
double Length(const Vector& A){ return sqrt(Dot(A, A)); } //向量长度
double Angle(const Vector& A, const Vector& B) { return acos(Dot(A, B)/Length(A)/Length(B)); } //AB向量夹角
double Cross(const Vector& A, const Vector& B) { return A.x*B.y - A.y*B.x; } //AB叉积 有向面积
double Area(const Point& A, const Point& B, const Point& C) { return fabs(Cross(B-A, C-A)); }
//向量旋转 rad正表示逆时针 反之顺时针
Vector Rotate(Vector A,double rad){ return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}
//A不能是0向量
Vector normal(Vector A) { return Point(-A.y, A.x) / Length(A);} //向量A的单位法向量，即A左转90度 以后把长度归归一化
double angle(Vector A) { return atan2(A.y, A.x);} //向量极角 向量A与x轴的夹角
Vector vecunit(Vector A){ return A / Length(A);} //单位向量 struct Line {
Point P; //直线上一点
Vector dir; //方向向量(半平面交中该向量左侧表示相应的半平面)
double ang; //极角，即从x正半轴旋转到向量dir所需要的角（弧度） Line() { } //构造函数
Line(const Line& L): P(L.P), dir(L.dir), ang(L.ang) { }
Line(const Point& P, const Vector& dir): P(P), dir(dir) { ang = atan2(dir.y, dir.x); } bool operator < (const Line& L) const { //极角排序
return ang < L.ang;
}
Point point(double t) { return P + dir*t; }
}; //直线交点1 P+tv Q+tw
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w)
{
Vector u=P-Q;
double t = Cross(w,u)/Cross(v,w);
return P+v*t;
}
//直线交点2
Point GetIntersection(Line a, Line b)
{
Vector u = a.P-b.P;
double t = Cross(b.dir, u) / Cross(a.dir, b.dir);
return a.P + a.dir*t;
}
bool SegmentProperInntersection(Point a1,Point a2,Point b1,Point b2)//线段相交判定
{
double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),
c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<&&dcmp(c3)*dcmp(c4)<;
}
double DistanceToSegment(Point P,Point A,Point B) //点P到线段AB的距离
{
if(A==B) return Length(P-A);
Vector v1 = B - A,v2 = P - A,v3 = P - B;
if(dcmp(Dot(v1,v2))<) return Length(v2);
else if(dcmp(Dot(v1,v3))>) return Length(v3);
else return fabs(Cross(v1,v2))/Length(v1);
}
Point GetLineProjection(Point P,Point A,Point B) //点P在直线AB上的投影
{
Vector v = B-A;
return A+v*(Dot(v,P-A)/Dot(v,v));
}
bool OnSegment(Point p, Point a1, Point a2) //判断点是否在线段a1a2上 不含端点
{
return dcmp(Cross(a1-p, a2-p)) == && dcmp(Dot(a1-p, a2-p)) < ;
} struct Circle {
Point c; //圆心
double r; //半径 Circle() { }
Circle(const Circle& rhs): c(rhs.c), r(rhs.r) { }
Circle(const Point& c, const double& r): c(c), r(r) { } Point point(double ang) const { return Point(c.x + cos(ang)*r, c.y + sin(ang)*r); } //圆心角所对应的点
double area(void) const { return PI * r * r; }
};
bool InCircle(Point x, Circle c)
{
return dcmp(c.r*c.r - Length(c.c - x)*Length(c.c - x)) >= ;
}
//直线与圆的交点
int getLineCircleIntersection(Line L, Circle C, Point* sol) //函数返回交点个数 sol数组存放交点
{
Vector nor = normal(L.dir);
Line pl = Line(C.c, nor);
Point ip = GetIntersection(pl, L);
double dis = Length(ip - C.c);
if (dcmp(dis - C.r) > ) return ;
Point dxy = vecunit(L.dir) * sqrt(C.r*C.r - dis*dis);
int ret = ;
sol[ret] = ip + dxy;
if (OnSegment(sol[ret], L. P, L.point())) ret++;
sol[ret] = ip - dxy;
if (OnSegment(sol[ret], L.P, L.point())) ret++;
return ret;
}
//圆与圆的交点
int getCircleCircleIntersection(Circle C1,Circle C2,vector<Point>& sol)//函数返回交点个数 sol数组存放交点
{
double d=Length(C1.c-C2.c);
if(dcmp(d)==){
if(dcmp(C1.r-C2.r)==) return -;//两圆重合
return ;
}
if(dcmp(C1.r+C2.r-d)<) return ;
if(dcmp(fabs(C1.r-C2.r)-d)>) return ; double a=angle(C2.c-C1.c);
double da=acos((C1.r*C1.r+d*d-C2.r*C2.r)/(*C1.r*d));
Point p1=C1.point(a-da),p2=C1.point(a+da);
sol.push_back(p1);
if(p1==p2) return ;
sol.push_back(p2);
return ;
}
//过点p到圆c的切线
int getTangents(Point p,Circle C,Vector* v)//函数返回条数,v[i]是第i条切线的向量
{
Vector u=C.c-p;
double dist=Length(u);
if(dist<C.r) return ; //点在圆内
else if(dcmp(dist-C.r)==){//p在圆c上，只有一条切线
v[]=Rotate(u,PI/);
return ;
}else{
double ang = asin(C.r/dist);
v[]=Rotate(u,-ang);
v[]=Rotate(u,ang);
return ;
}
}
//两圆的公切线
int getTangents(Circle A,Circle B,Point* a,Point* b)
{
int cnt=;
if(A.r<B.r){swap(A,B);swap(a,b);}
double d2=(A.c.x-B.c.x)*(A.c.x-B.c.x)+(A.c.y-B.c.y)*(A.c.y-B.c.y);
double rdiff=A.r - B.r;
double rsum=A.r + B.r;
if(d2<rdiff*rdiff) return ;//内含 double base = atan2(B.c.y-A.c.y,B.c.x-A.c.x);
if(dcmp(d2)==&&dcmp(A.r-B.r)==) return -;//两圆重合,无数条切线
if(dcmp(d2-rdiff*rdiff)==){ //内切,1条切线
a[cnt]=A.point(base);b[cnt]=B.point(base);cnt++;
return ;
}
//有外公切线
double ang=acos((A.r-B.r)/sqrt(d2));
a[cnt] = A.point(base+ang);b[cnt] = B.point(base+ang);cnt++;
a[cnt] = A.point(base-ang);b[cnt] = B.point(base-ang);cnt++;
if(dcmp(d2-rsum*rsum)==){ //一条内公切线
a[cnt]=b[cnt]=A.point(base);cnt++;
}
else if(dcmp(d2-rsum*rsum)>){ //两条内公切线
ang = acos((A.r+B.r)/sqrt(d2));
a[cnt] = A.point(base+ang);b[cnt] = B.point(PI+base+ang);cnt++;
a[cnt] = A.point(base-ang);b[cnt] = B.point(PI+base-ang);cnt++;
}
return cnt;
}
double SegCircleArea(Circle C, Point a, Point b) //线段切割圆
{
double a1 = angle(a - C.c);
double a2 = angle(b - C.c);
double da = fabs(a1 - a2);
if (da > PI) da = PI * 2.0 - da;
return dcmp(Cross(b - C.c, a - C.c)) * da * sqr(C.r) / 2.0;
} double PolyCiclrArea(Circle C, Point *p, int n)//多边形与圆相交面积
{
double ret = 0.0;
Point sol[];
p[n] = p[];
for(int i=;i<n;i++)
{
double t1, t2;
int cnt = getLineCircleIntersection(Line(p[i], p[i+]-p[i]), C, sol);
if (cnt == )
{
if (!InCircle(p[i], C) || !InCircle(p[i+], C)) ret += SegCircleArea(C, p[i], p[i+]);
else ret += Cross(p[i+] - C.c, p[i] - C.c) / 2.0;
}
if (cnt == )
{
if (InCircle(p[i], C) && !InCircle(p[i+], C)) ret += Cross(sol[] - C.c, p[i] - C.c) / 2.0, ret += SegCircleArea(C, sol[], p[i+]);
else ret += SegCircleArea(C, p[i], sol[]), ret += Cross(p[i+] - C.c, sol[] - C.c) / 2.0;
}
if (cnt == )
{
if ((p[i] < p[i + ]) ^ (sol[] < sol[])) swap(sol[], sol[]);
ret += SegCircleArea(C, p[i], sol[]);
ret += Cross(sol[] - C.c, sol[] - C.c) / 2.0;
ret += SegCircleArea(C, sol[], p[i+]);
}
}
return fabs(ret);
}
double PolygonArea(Point *po, int n) //多边形面积
{
double area = 0.0;
for(int i = ; i < n-; i++) {
area += Cross(po[i]-po[], po[i+]-po[]);
}
return area * 0.5;
}
//-----------------------------------------------------------------------------------
Point p[maxn];
int main()
{
double a,w,h;
int n;
cin>>a>>w>>h>>n;
double ang=a/*PI;
double minx=inf,maxx=-1.0;
double miny=inf,maxy=-1.0;
for(int i=;i<n;i++)
{
p[i].in();
p[i]=p[]+Rotate(p[i]-p[],ang);
minx=min(minx,p[i].x);
miny=min(miny,p[i].y);
maxx=max(maxx,p[i].x);
maxy=max(maxy,p[i].y);
}
double dux=w/(maxx-minx);
double duy=h/(maxy-miny);
for(int i=;i<n;i++)
{
p[i].x-=minx;
p[i].y-=miny;
p[i].x*=dux;
p[i].y*=duy;
p[i].out();
}
}
I
题意：给出n个狗的坐标，m个碗的坐标和碗里的数的数量w L(升) , 狗每一秒可以走一个单位长度，狗喝水需要10s ，问S秒内每只狗从自己的位置出发是否全部都能喝完1L水。
题解：如果距离在时限内狗和碗连边，碗拆点就可以了。源点汇点不说了，很简单。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+,mod=1e9+,inf=0x3f3f3f3f;
typedef long long ll;
struct edge
{
int from,to,c,f;
edge(int u,int v,int c,int f):from(u),to(v),c(c),f(f) {}
};
int n,m;
vector<edge> edges;
vector<int> g[maxn];
int d[maxn];//从起点到i的距离
int cur[maxn];//当前弧下标
void init(int N)
{
for(int i=; i<=N; i++) g[i].clear();
edges.clear();
}
void addedge(int from,int to,int c) //加边 支持重边
{
edges.push_back(edge(from,to,c,));
edges.push_back(edge(to,from,,));
int siz=edges.size();
g[from].push_back(siz-);
g[to].push_back(siz-);
}
int bfs(int s,int t) //构造一次层次图
{
memset(d,-,sizeof(d));
queue<int> q;
q.push(s);
d[s]=;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=;i<g[x].size();i++)
{
edge &e=edges[g[x][i]];
if(d[e.to]<&&e.f<e.c) //d[e.to]=-1表示没访问过
{
d[e.to]=d[x]+;
q.push(e.to);
}
}
}
return d[t];
}
int dfs(int x,int a,int t) // a表示x点能接收的量
{
if(x==t||a==)return a;
int flow=,f;//flow总的增量 f一条增广路的增量
for(int &i=cur[x];i<g[x].size();i++)//cur[i] &引用修改其值 从上次考虑的弧
{
edge &e=edges[g[x][i]];
if(d[x]+==d[e.to]&&(f=dfs(e.to,min(a,e.c-e.f),t))>) //按照层次图增广 满足容量限制
{
e.f+=f;
edges[g[x][i]^].f-=f; //修改流量
flow+=f;
a-=f;
if(a==) break;
}
}
return flow;
}
int maxflow(int s,int t)
{
int flow=;
while(bfs(s,t)!=-) //等于-1代表构造层次图失败 结束
{
memset(cur,,sizeof(cur));
flow+=dfs(s,inf,t);
}
return flow;
}
struct node
{
ll first,second;
}dog[maxn],bowl[maxn];
int num[maxn];
ll s;
int main()
{
while(scanf("%d%d%lld",&n,&m,&s)!=EOF)
{
init(n+*m+);
for(int i=;i<=n;i++)
scanf("%lld%lld",&dog[i].first,&dog[i].second);
for(int i=;i<=m;i++)
scanf("%lld%lld%d",&bowl[i].first,&bowl[i].second,&num[i]);
for(int i=;i<=n;i++)
{
addedge(,i,);
for(int j=;j<=m;j++)
{
if(sqrt(pow(abs(dog[i].first-bowl[j].first),)+pow(abs(dog[i].second-bowl[j].second),))+<=s)
addedge(i,n+j,);
}
}
for(int j=;j<=m;j++)
addedge(n+j,n+m+j,num[j]),
addedge(n+m+j,n+*m+,inf);
if(maxflow(,n+m*+)==n)
printf("YES\n");
else
printf("NO\n");
}
}