oj.uz

답안 #632509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
632509 2022-08-20T08:31:10 Z andrei_boaca Printed Circuit Board (CEOI12_circuit) C++14
30 / 100
 100 ms 10048 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
int n;
struct point
{
    int x,y,ang;
} v[100005],angle[100005];
bool comp(point a, point b)
{
    return a.y*b.x<a.x*b.y;
}
map<pii,int> nrm;
bool cmp(int a, int b)
{
    if(v[a].ang!=v[b].ang)
        return v[a].ang<v[b].ang;
    return v[a].y<v[b].y;
}
bool use[100005],spec[100005];
int aib[100005],times[100005];
int lsb(int x)
{
    return x&(-x);
}
void update(int poz,int val)
{
    for(int i=poz;i<=n;i+=lsb(i))
        aib[i]+=val;
}
int suma(int poz)
{
    int rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
int cur=0;
bool iseq(point a, point b)
{
    return a.x==b.x&&a.y==b.y;
}
ll aria(point A, point B)
{
    ll rez=1LL*A.x*B.y-1LL*A.y*B.x;
    rez=abs(rez);
    return rez;
}
bool intersect(point A, point B, point C)
{
    if(iseq(A,C)||iseq(B,C))
        return 0;

    ll a1=B.y-A.y;
    ll b1=A.x-B.x;
    ll c1=-a1*A.x-b1*A.y;

    ll a2=C.y;
    ll b2=-C.x;
    ll c2=0;

    ld coef=a2*b1-a1*b2;
    if(coef==0)
        return 0;
    ld y=ld(-a2*c1)/coef;
    ld x=ld(-b2*y)/a2;
    if(x>=min(A.x,B.x)&&x<=max(A.x,B.x)&&x<=C.x&&x>=0)
        if(y>=min(A.y,B.y)&&y<=max(A.y,B.y)&&y<=C.y&&y>=0)
            return 1;
    return 0;
}
bool checkgood(int i)
{
    if(cur==0)
        return 1;
    point a=v[cur];
    int lft=cur-1;
    if(lft<1)
        lft=n;
    point b=v[lft];
    if(intersect(a,b,v[i]))
        return 0;
    int rgt=cur+1;
    if(rgt>n)
        rgt=1;
    b=v[rgt];
    if(intersect(a,b,v[i]))
        return 0;
    return 1;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        v[i]={x,y,0};
        int cmmdc=__gcd(x,y);
        x/=cmmdc;
        y/=cmmdc;
        angle[i]={x,y,0};
    }
    sort(angle+1,angle+n+1,comp);
   // cout<<'\n';
    for(int i=1;i<=n;i++)
    {
        pii a={angle[i].x,angle[i].y};
        nrm[a]=i;
    }
    for(int i=1;i<=n;i++)
    {
        int cmmdc=__gcd(v[i].x,v[i].y);
        int xa=v[i].x/cmmdc,ya=v[i].y/cmmdc;
        v[i].ang=nrm[{xa,ya}];
    }
    vector<int> ind;
    for(int i=1;i<=n;i++)
        ind.push_back(i);
    sort(ind.begin(),ind.end(),cmp);
    vector<int> sol;
    int nr=0;
    for(int i:ind)
    {
        nr++;
        bool good=checkgood(i);
        if(good)
        {
            cur=i;
            sol.push_back(i);
        }
    }
    sort(sol.begin(),sol.end());
    cout<<sol.size()<<'\n';
    for(int i:sol)
        cout<<i<<' ';
    return 0;
}

Compilation message

circuit.cpp: In function 'bool intersect(point, point, point)':
circuit.cpp:63:8: warning: unused variable 'c2' [-Wunused-variable]
   63 |     ll c2=0;
      |        ^~

Subtask #1
30.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Incorrect 15 ms 1288 KB Output isn't correct
6 Incorrect 14 ms 1276 KB Output isn't correct
7 Incorrect 30 ms 2292 KB Output isn't correct
8 Incorrect 11 ms 1108 KB Output isn't correct
9 Correct 8 ms 980 KB Output is correct
10 Incorrect 18 ms 1284 KB Output isn't correct
11 Incorrect 16 ms 1448 KB Output isn't correct
12 Correct 20 ms 2160 KB Output is correct
13 Incorrect 42 ms 3188 KB Output isn't correct
14 Incorrect 41 ms 4104 KB Output isn't correct
15 Correct 66 ms 5000 KB Output is correct
16 Execution timed out 132 ms 9532 KB Time limit exceeded
17 Execution timed out 168 ms 10048 KB Time limit exceeded
18 Runtime error 59 ms 5084 KB Execution killed with signal 11
19 Runtime error 60 ms 5128 KB Execution killed with signal 11
20 Execution timed out 130 ms 8384 KB Time limit exceeded