头像

溪染




离线:2天前


新鲜事 原文

溪染
25天前
WC考完了 颓废开始了 [颓废入口](http://tool.liumingye.cn/music/?page=audioPage&type=YQD&name=%E6%98%9F%E6%98%9F%E5%9C%A8%E5%94%B1%E6%AD%8C%20-%20%E5%8F%B8%E5%8D%97%2FCMJ%2FMango%20Daddy)



溪染
1个月前
#include<bits/stdc++.h>
using namespace std;
const int N=4e6+7;
struct oppo{
    int to,nex;
}rod[N];
int head[N],tot;
void add(int from,int to)
{
    rod[++tot].to=to;
    rod[tot].nex=head[from];
    head[from]=tot;
}
int n,m;
int dfn[N],low[N],all;
int in[N];
int stk[N],hh;
int clo[N],clo_tot;
void dfs(int x)
{
    dfn[x]=low[x]=++all;
    stk[++hh]=x;in[x]=1;
    for(int i=head[x];i;i=rod[i].nex){
        int to=rod[i].to;
        if(!dfn[to]){
            dfs(to);
            low[x]=min(low[to],low[x]);
        }else if(dfn[to]&&in[to])
            low[x]=min(low[x],dfn[to]);
    }
    if(low[x]==dfn[x]){
        ++clo_tot;
        while(stk[hh+1]!=x){
            clo[stk[hh]]=clo_tot;
            in[stk[hh]]=0;
            hh--;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,a,y,b;
        scanf("%d%d%d%d",&x,&a,&y,&b);
        x*=2;y*=2;
        add(x|(!a),y|b);//若xa不选,yb必选
        add(y|(!b),x|a);//若yb不选,xa必选
    }
    for(int i=2;i<=2*n+1;i++)
        if(!dfn[i])
            dfs(i);
    for(int i=1;i<=n;i++)
        if(clo[i*2]==clo[i*2+1]){
            puts("IMPOSSIBLE");
            return 0;
        }
    puts("POSSIBLE");
    for(int i=1;i<=n;i++)
        cout<<(clo[i*2]>clo[i*2+1])<<" ";
    return 0;
}


新鲜事 原文

溪染
1个月前
计算几何66行的代码,我愣是调了4个小时 哭了:(



溪染
1个月前
#include<bits/stdc++.h>
using namespace std;
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 b){return point(x*b,y*b);}
    double operator%(point b){return x*b.y-y*b.x;}
}d[1010];
struct line{
    point st,ed;
    double get_slope(){return atan2((ed-st).y,(ed-st).x);}
    bool operator<(line b){
        double a=this->get_slope();
        double c=b.get_slope();
        if(fabs(a-c)>1e-8)
            return a<c;
        return (b.st-st)%(b.ed-st)>0;
    }
}p[1010];
point get_intersection(line s,line t){
    double k=((t.ed-t.st)%(s.st-t.st))/((s.ed-s.st)%(t.ed-t.st));
    return s.st+(s.ed-s.st)*k;
}
bool is_right(point a,line b){
    return (a-b.st)%(b.ed-b.st)>=0;
}
int cnt,n,stk[1010],hh=-1,tt;
double work(){
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++){
        if(i!=1&&fabs(p[i].get_slope()-p[i-1].get_slope())<1e-8) continue;
        while(tt+1<=hh && is_right(get_intersection(p[stk[hh]],p[stk[hh-1]]),p[i])) hh--;
        while(tt+1<=hh && is_right(get_intersection(p[stk[tt]],p[stk[tt+1]]),p[i])) tt++;
        stk[++hh]=i;
    }
    while(tt+1<=hh && is_right(get_intersection(p[stk[hh]],p[stk[hh-1]]),p[stk[tt]])) hh--;
    while(tt+1<=hh && is_right(get_intersection(p[stk[tt]],p[stk[tt+1]]),p[stk[hh]])) tt++;
    stk[++hh]=stk[tt];
    int k=0;
    for(int i=tt;i<hh;i++)
        d[++k] = get_intersection(p[stk[i]],p[stk[i+1]]);
    double res=0;
    for(int i=1;i<=k;i++)
        res+=d[i]%d[i%k+1];
    return fabs(res/2);
}
int main(){
    cin>>cnt;
    for(int i=1;i<=cnt;i++){
        int m;
        scanf("%d",&m);
        for(int j=0;j<m;j++)
            scanf("%lf%lf",&d[j].x,&d[j].y);
        for(int j=0;j<m;j++){
            p[++n].st=d[j];
            p[n].ed=d[(j+1)%m];
        }
    }
    double ans=work();
    ans= ans==ans?ans:0;
    printf("%.3lf",ans);
    return 0;
}



溪染
1个月前
#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
struct point{
    double x,y;
    point(){};
    point(double x,double y):x(x),y(y){};
    double operator%(point b){
        return x*b.y-y*b.x;
    }
    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 rotate(double s){
        return point(x*cos(s)-y*sin(s),y*cos(s)+x*sin(s));
    }
    bool operator<(point b){
        return x<b.x;
    }
}p[40010];
double distanc(point a,point b)
{
    return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
int n;
double a,b,r;
int stk[40010];
bool uers[40010];
double work()
{
    int tp=0;
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++){
        while(tp>=2&&((p[stk[tp]]-p[stk[tp-1]]) % (p[i]-p[stk[tp-1]]))>=0)
            uers[stk[tp--]]=0;
        uers[i]=1;
        stk[++tp]=i;
    }
    uers[1]=0;
    for(int i=n;i>=1;i--){
        if(uers[i]) continue;
        while(tp>=2&&((p[stk[tp]]-p[stk[tp-1]]) % (p[i]-p[stk[tp-1]]))>=0)
            tp--;
        stk[++tp]=i;
    }
    double ans=0;
    for(int i=2;i<=tp;i++)
        ans+=distanc(p[stk[i]],p[stk[i-1]]);
    return ans;
}
int main()
{
    cin>>n;
    cin>>b>>a>>r;
    for(int i=1;i<=n;i++){
        double x,y,s;
        scanf("%lf%lf%lf",&x,&y,&s);
        point st=point(x,y);
        p[4*i-3]=st+point(a/2-r,b/2-r).rotate(s);
        p[4*i-2]=st+point(-a/2+r,b/2-r).rotate(s);
        p[4*i-1]=st+point(a/2-r,-b/2+r).rotate(s);
        p[4*i-0]=st+point(-a/2+r,-b/2+r).rotate(s);
    }
    n=4*n;
    printf("%.2lf",work()+acos(-1)*r*2);
    return 0;
}



溪染
1个月前

当你把长和宽读反了
但是你可以获得80分的好成绩
(不要问我怎么知道有80分)




溪染
1个月前
#include<bits/stdc++.h>
using namespace std;
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);
    }
    double operator%(Point b){
        return x*b.y-y*b.x;//叉乘 
    }
    bool operator<(Point b){
        return x<b.x;
    }
}p[10005];
int n;
int stk[10005];
bool uers[10005];
double distanc(Point a,Point b)
{
    return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
double work()//求凸包  
{
    int tp=0;
    for(int i=1;i<=n;i++){
        while(tp>=2&&((p[stk[tp]]-p[stk[tp-1]])%(p[i]-p[stk[tp-1]]))>0)
            uers[stk[tp--]]=0;
        uers[i]=1;
        stk[++tp]=i;
    }
    uers[1]=0;
    for(int i=n;i>=1;i--){
        if(uers[i]) continue;
        while(tp>=2&&((p[stk[tp]]-p[stk[tp-1]])%(p[i]-p[stk[tp-1]]))>0)
            tp--;
        stk[++tp]=i;
    }
    double ans=0;
    for(int i=2;i<=tp;i++)
        ans+=distanc(p[stk[i]],p[stk[i-1]]);
    return ans;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        double x,y;
        scanf("%lf%lf",&x,&y);
        p[i]=Point(x,y);
    }
    sort(p+1,p+n+1);
    printf("%.2lf",work());
    return 0;
}



溪染
1个月前

定义了点,向量的结构体,重载运算符
二分判断即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct oppo{
    int x,y;
    oppo(){};
    oppo(int x,int y):x(x),y(y){};
    oppo operator -(){
        return oppo(-x,-y);
    }
    oppo operator -(oppo b){
        return oppo(x-b.x,y-b.y);
    }
    oppo operator +(oppo b){
        return oppo(x+b.x,y+b.y);
    }
    oppo operator *(int b){
        return oppo(x*b,y*b);
    }
    int operator *(oppo b){
        return x*b.x+y*b.y;//点乘 
    }
    int operator ^(oppo b){
        return x*b.y-y*b.x;//叉乘 
    }
    oppo operator /(int b){
        return oppo(x/b,y/b);
    }
    void out(){
        printf("(%lld,%lld)\n",x,y);
    }
}p[10000][3];
int tot[10000];
int n,m,x,y,xx,yy; 
void find(oppo k)
{
    int l=1,r=n,mid,ans=0;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(((k-p[mid][0])^(p[mid][1]-p[mid][0]))>=0){
            ans=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    tot[ans]++;
}
int T;
signed main()
{
    while(++T)
    {
        scanf("%lld",&n);if(!n) break;
        if(T!=1) puts("");
        scanf("%lld%lld%lld%lld%lld",&m,&x,&y,&xx,&yy);
        memset(tot,0,sizeof(tot));
        for(int i=1;i<=n;i++){
            int a,b;
            scanf("%lld%lld",&a,&b);
            p[i][1]=oppo(a,y);
            p[i][0]=oppo(b,yy);
        }
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%lld%lld",&a,&b);
            find(oppo(a,b));
        }
        for(int i=0;i<=n;i++)
            printf("%lld: %lld\n",i,tot[i]);
    }
    return 0;
}



溪染
1个月前

gethub地址: https://github.com/forthespada/CS-Books
预览(还有一部分没有截图上来):
QQ截图20210120082418.png



问题 测评环境

溪染
1个月前

ACwing的测评是在windows环境下测评的吗?