E. The Supersonic Rocket Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)

http://codeforces.com/contest/1017/problem/E

凸包模板+kmp

 #include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <time.h>
#include <string>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <ext/rope>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#define minv 1e-10
#define inf 1e9
#define pi 3.1415926536
#define E 2.7182818284
const ll mod=1e9+;//
const int maxn=1e5+; struct node
{
ll x,y;
}a[maxn],b[maxn],e[maxn],f[maxn],point; int p[maxn*];
double c[maxn*],d[maxn*]; ///result only 1/0
int cmp(node a,node b)
{
ll s=(a.y-point.y)*(b.x-point.x) - (b.y-point.y)*(a.x-point.x);
if (s<)
return ;
else if (s>)
return ;
else
return pow(a.y-point.y,)+pow(a.x-point.x,) < pow(b.y-point.y,)+pow(b.x-point.x,);
} void work(node a[],double c[],node e[],int n,int* z)
{
int i,g;
for (i=;i<=n;i++)
{
scanf("%lld%lld",&a[i].x,&a[i].y);
if (a[].x>a[i].x || (a[].x==a[i].x && a[].y>a[i].y))
swap(a[i],a[]);
}
point=a[];
sort(a+,a+n+,cmp); e[].x=a[].x,e[].y=a[].y;
e[].x=a[].x,e[].y=a[].y;
g=;
for (i=;i<=n;i++)
{
while (g> && (a[i].x-e[g-].x)*(e[g].y-e[g-].y)-(e[g].x-e[g-].x)*(a[i].y-e[g-].y)>=)
g--;
g++;
e[g].x=a[i].x,e[g].y=a[i].y;
}
e[g+]=e[];
e[]=e[g]; for (i=;i<=g;i++)
{
//len^2 cos(angle)
c[i*-]=(double)(pow(e[i+].x-e[i].x,) + pow(e[i+].y-e[i].y,)); ll b1=pow(e[i+].y-e[i].y,)+pow(e[i+].x-e[i].x,),
b2=pow(e[i-].y-e[i].y,)+pow(e[i-].x-e[i].x,),
b3=pow(e[i+].y-e[i-].y,)+pow(e[i+].x-e[i-].x,); c[i*]=1.0*(b1+b2-b3)//sqrt(b1)/sqrt(b2);
}
(*z)=g*;
} int main()
{
int n,m,g1,g2,i,j;
scanf("%d%d",&n,&m);
work(a,c,e,n,&g1);
work(b,d,f,m,&g2);
if (g1!=g2)
{
printf("NO");
return ;
}
for (i=;i<=g2;i++)
d[i+g2]=d[i];
g2<<=; p[]=;
j=;
for (i=;i<=g1;i++)
{
while (j> && fabs(c[j+]-c[i])>minv)
j=p[j];
if (fabs(c[j+]-c[i])<minv)
j++;
p[i]=j;
} j=;
for (i=;i<=g2;i++)
{
while (j> && fabs(c[j+]-d[i])>minv)
j=p[j];
if (fabs(c[j+]-d[i])<minv)
j++;
if (j==g1)
{
printf("YES");
return ;
}
}
printf("NO");
return ;
}
/*
6 5
1 100000000
2 100000000
3 100000000
4 100000000
5 100000000
6 1 2 100000000
6 1
3 100000000
1 100000000
5 100000000
*/
上一篇:代码实现SQL Server动态行转列,不用存储过程


下一篇:老生常谈之SQL Server (行转列,列转行)